Advertisement
Guest User

FormulaOrder

a guest
Sep 21st, 2019
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 6.83 KB | None | 0 0
  1. import java.util.Arrays;
  2. import java.util.ArrayList;
  3. import java.util.HashMap;
  4. import java.util.Scanner;
  5.  
  6. public class FormulaOrder {
  7.     private static String ops = "+-*/(),=";
  8.     private static HashMap<String, Integer> dict = new HashMap<>();
  9.     private static ArrayList<Formula> forms = new ArrayList<>();
  10.     private static ArrayList<Integer> order = new ArrayList<>();
  11.  
  12.     private static void dfs(int n){
  13.         forms.get(n).color = 1;
  14.         for (int i = 0; i < forms.get(n).to.size(); i++) {
  15.             int to = forms.get(n).to.get(i);
  16.             if(forms.get(to).color != 2){
  17.                 if(forms.get(to).color == 1){
  18.                     System.out.print("cycle");
  19.                     System.exit(0);
  20.                 } else{
  21.                     dfs(to);
  22.                 }
  23.             }
  24.         }
  25.         order.add(n);
  26.         forms.get(n).color = 2;
  27.     }
  28.  
  29.     public static void main(String[] args){
  30.         Scanner in = new Scanner(System.in);
  31.         while(in.hasNext()){
  32.             forms.add(new Formula(in.nextLine()));
  33.         }
  34.         for(int i = 0; i < forms.size(); i++){
  35.             for (String var : forms.get(i).vars) {
  36.                 if(!dict.containsKey(var)) dict.put(var, i);
  37.                 else error();
  38.             }
  39.         }
  40.         for(int i = 0; i < forms.size(); i++){
  41.             for (String subvar : forms.get(i).subvars) {
  42.                 if(dict.containsKey(subvar)) forms.get(i).to.add(dict.get(subvar));
  43.                 else error();
  44.             }
  45.         }
  46.         for(int i = 0; i < forms.size(); i++){
  47.             if(forms.get(i).color == 0) dfs(i);
  48.         }
  49.         for (int i : order) {
  50.             System.out.println(forms.get(i).form);
  51.         }
  52.     }
  53.  
  54.     private static void error(){
  55.         System.out.println("syntax error");
  56.         System.exit(0);
  57.     }
  58.  
  59.     private static class Formula{
  60.         String form;
  61.         ArrayList<Token> tokens;
  62.         ArrayList<String> vars, subvars;
  63.         ArrayList<Integer> to;
  64.         int color, current, formCount;
  65.  
  66.         public Formula(String form){
  67.             this.form = form;
  68.             vars = new ArrayList<>();
  69.             subvars = new ArrayList<>();
  70.             to = new ArrayList<>();
  71.             tokens = new ArrayList<>();
  72.             color = 0;
  73.             formCount = 0;
  74.             lexer();
  75.             parseFormula();
  76.             if(current != tokens.size() - 1 || formCount != vars.size()) error();
  77.         }
  78.  
  79.         private void lexer(){
  80.             current = 0;
  81.             do{
  82.                 if(form.charAt(current) == ' '){
  83.                     current++;
  84.                     continue;
  85.                 }
  86.                 if(ops.contains(Character.toString(form.charAt(current)))){
  87.                     tokens.add(new Token(1, Character.toString(form.charAt(current))));
  88.                 }else if(Character.isDigit(form.charAt(current))){
  89.                     tokens.add(new Token(0, getNumber()));
  90.                 }else if(Character.isAlphabetic(form.charAt(current))){
  91.                     tokens.add(new Token(2, getId()));
  92.                 }else error();
  93.                 current++;
  94.             }while(current < form.length());
  95.         }
  96.  
  97.         private String getId(){
  98.             int begin = current;
  99.             while(current + 1 < form.length() && (Character.isAlphabetic(form.charAt(current + 1)) || Character.isDigit(form.charAt(current + 1)))){
  100.                 current++;
  101.             }
  102.             return form.substring(begin, current+1);
  103.         }
  104.  
  105.         private String getNumber(){
  106.             int begin = current;
  107.             while(current + 1 < form.length() && Character.isDigit(form.charAt(current + 1))){
  108.                 current++;
  109.             }
  110.             return form.substring(begin, current+1);
  111.         }
  112.  
  113.         private void parseFormula(){
  114.             current = 0;
  115.             parseIdents();
  116.             if(peek().name.equals("=")){
  117.                 current+=2;
  118.                 parseExprs();
  119.             } else error();
  120.         }
  121.  
  122.         private void parseIdents(){
  123.             if(current >= tokens.size()) error();
  124.             if(tokens.get(current).type == 2) vars.add(tokens.get(current).name); else error();
  125.             if (peek().name.equals(",")){
  126.                 current+=2;
  127.                 parseIdents();
  128.             }
  129.         }
  130.  
  131.         private void parseExprs(){
  132.             formCount++;
  133.             if(current >= tokens.size()) error();
  134.             parseE();
  135.             if (peek().name.equals(",")){
  136.                 current+=2;
  137.                 parseExprs();
  138.             }
  139.         }
  140.  
  141.         private void parseE(){
  142.             if(current >= tokens.size()) error();
  143.             parseT();
  144.             if(peek().name.equals("+") || peek().name.equals("-")){
  145.                 current+=2;
  146.                 parseE2();
  147.             }
  148.         }
  149.  
  150.         private void parseE2(){
  151.             if(current >= tokens.size()) error();
  152.             parseT();
  153.             if(peek().name.equals("+") || peek().name.equals("-")){
  154.                 current+=2;
  155.                 parseE2();
  156.             }
  157.         }
  158.  
  159.         private void parseT(){
  160.             if(current >= tokens.size()) error();
  161.             parseF();
  162.             if(peek().name.equals("*") || peek().name.equals("/")){
  163.                 current+=2;
  164.                 parseT2();
  165.             }
  166.         }
  167.  
  168.         private void parseT2(){
  169.             if(current >= tokens.size()) error();
  170.             parseF();
  171.             if(peek().name.equals("*") || peek().name.equals("/")){
  172.                 current+=2;
  173.                 parseT2();
  174.             }
  175.         }
  176.  
  177.         private void parseF(){
  178.             if(current >= tokens.size()) error();
  179.             if(tokens.get(current).type == 0){
  180.             }else if(tokens.get(current).type == 2){
  181.                 subvars.add(tokens.get(current).name);
  182.             }else if(tokens.get(current).name.equals("(")){
  183.                 current++;
  184.                 parseE();
  185.                 if (peek().name.equals(")")) current++;
  186.                 else error();
  187.             }else if(tokens.get(current).name.equals("-")){
  188.                 current++;
  189.                 parseF();
  190.             }else error();
  191.         }
  192.  
  193.         private Token peek(){
  194.             if(current+1 < tokens.size()) return tokens.get(current+1);
  195.             return new Token();
  196.         }
  197.  
  198.         private class Token{
  199.             int type;
  200.             String name;
  201.             int value;
  202.  
  203.             private Token(int type, String value){
  204.                 this.type = type;
  205.                 if(type == 0){
  206.                     this.value = Integer.parseInt(value);
  207.                     this.name = "";
  208.                 }
  209.                 else this.name = value;
  210.             }
  211.  
  212.             private Token(){
  213.                 type = -1;
  214.                 name = "";
  215.             }
  216.         }
  217.     }
  218. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement