Advertisement
Guest User

Untitled

a guest
Sep 27th, 2016
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 10.95 KB | None | 0 0
  1. import java.util.*;
  2. import java.util.function.IntPredicate;
  3.  
  4. public class FormulaOrder {
  5.  
  6.     private static int t = 1;
  7.  
  8.     private static void dfs (Formula f) {
  9.         f.setT1(t++);
  10.         f.setT2(-1);
  11.         for (Formula e : f.getDependencies()) {
  12.             if (e.getT1() == 0)
  13.                 dfs(e);
  14.             if (e.getT2() == -1) {
  15.                 System.out.println("cycle");
  16.                 System.exit(1);
  17.             }
  18.         }
  19.         f.setT2(t++);
  20.     }
  21.  
  22.     public static void main (String[] args) {
  23.  
  24.         Scanner scn = new Scanner(System.in);
  25.         HashSet<String> undefs = new HashSet<>();
  26.  
  27.         HashMap<String, Formula> fProviders = new HashMap<>();
  28.         ArrayList<Formula> formulae = new ArrayList<>();
  29.  
  30.         while (scn.hasNextLine()) {
  31.  
  32.             Formula currentFormula = new Formula(scn.nextLine());
  33.             formulae.add(currentFormula);
  34.  
  35.             try {
  36.                 FormulaParser fp = new FormulaParser(currentFormula,
  37. undefs, fProviders);
  38.                 fp.parse();
  39.             }
  40.             catch (SyntaxError se) {
  41.                 System.out.println("syntax error");
  42.                 System.exit(1);
  43.             }
  44.         }
  45.  
  46.         if (!undefs.isEmpty()) {
  47.             System.out.println("syntax error");
  48.             System.exit(1);
  49.         }
  50.         formulae.stream().forEach(f -> f.fetchDependencies(fProviders));
  51.  
  52.         for (Formula f : formulae) {
  53.             if (f.getT1() == 0) {
  54.                 dfs(f);
  55.             }
  56.         }
  57.  
  58.         Collections.sort(formulae);
  59.  
  60.         for (Formula f : formulae)
  61.             System.out.println(f);
  62.  
  63.     }
  64.  
  65. }
  66.  
  67. class Formula implements Comparable<Formula> {
  68.  
  69.     private String formula;
  70.     private HashSet<String> dependsOn;
  71.     private ArrayList<Formula> dependencies;
  72.  
  73.     private int T1, T2;
  74.  
  75.     public Formula(String formula) {
  76.         this.formula = formula;
  77.         dependsOn = new HashSet<>();
  78.         dependencies = new ArrayList<>();
  79.     }
  80.  
  81.     public String getFormula () {
  82.         return formula;
  83.     }
  84.  
  85.     public void fetchDependencies (HashMap<String, Formula> providers) {
  86.         Iterator<String> dit = dependsOn.iterator();
  87.         while (dit.hasNext()) {
  88.             String curId = dit.next();
  89.             Formula corrFormula = providers.get(curId);
  90.             if (!dependencies.contains(corrFormula))
  91.                 dependencies.add(providers.get(curId));
  92.             dit.remove();
  93.         }
  94.     }
  95.  
  96.     public void addDependency (String ident) {
  97.         dependsOn.add(ident);
  98.     }
  99.  
  100.     public ArrayList<Formula> getDependencies () {
  101.         return dependencies;
  102.     }
  103.  
  104.     public int compareTo (Formula other) {
  105.         return Integer.compare(T2, other.T2);
  106.     }
  107.  
  108.     public int getT2() {
  109.         return T2;
  110.     }
  111.  
  112.     public void setT2(int t2) {
  113.         T2 = t2;
  114.     }
  115.  
  116.     public int getT1() {
  117.         return T1;
  118.     }
  119.  
  120.     public void setT1(int t1) {
  121.         T1 = t1;
  122.     }
  123.  
  124.     @Override
  125.     public String toString() {
  126.         return formula;
  127.     }
  128. }
  129.  
  130. class Position {
  131.  
  132.     private String formula;
  133.     private int index, line, col;
  134.  
  135.     public Position(String formula) {
  136.         this(formula, 0, 1, 1);
  137.     }
  138.  
  139.     private Position(String formula, int index, int line, int col) {
  140.         this.formula = formula;
  141.         this.index = index;
  142.         this.line = line;
  143.         this.col = col;
  144.     }
  145.  
  146.     public int getChar() {
  147.         return index < formula.length() ? formula.codePointAt(index) :
  148. -1;
  149.     }
  150.  
  151.     public boolean satisfies(IntPredicate p) {
  152.         return p.test(getChar());
  153.     }
  154.  
  155.     public Position skip() {
  156.         int c = getChar();
  157.         switch (c) {
  158.             case -1:
  159.                 return this;
  160.             case '\n':
  161.                 return new Position(formula, index + 1, line + 1, 1);
  162.             default:
  163.                 return new Position(formula, index + (c > 0xFFFF ? 2 :
  164. 1), line, col + 1);
  165.         }
  166.     }
  167.  
  168.     public static String getSubstring (Position start, Position follow)
  169. {
  170.         return start.formula.substring(start.index, follow.index);
  171.     }
  172.  
  173.     public Position skipWhile(IntPredicate p) {
  174.         Position pos = this;
  175.         while (pos.satisfies(p)) pos = pos.skip();
  176.         return pos;
  177.     }
  178.  
  179.     public String toString() {
  180.         return String.format("(%d, %d)", line, col);
  181.     }
  182. }
  183.  
  184. class SyntaxError extends Exception {
  185.     public SyntaxError(Position pos, String msg) {
  186.         super(String.format("Syntax error at %s: %s", pos.toString(),
  187. msg));
  188.     }
  189. }
  190.  
  191. enum Tag {
  192.     IDENT,
  193.     NUMBER,
  194.     EQUALSIGN,
  195.     LBRACKET,
  196.     RBRACKET,
  197.     PLUSSIGN,
  198.     MINUSSIGN,
  199.     COMMA,
  200.     MULSIGN,
  201.     DIVSIGN,
  202.     END_OF_TEXT
  203. }
  204.  
  205. class Token {
  206.     private Tag tag;
  207.     private Position start, follow;
  208.  
  209.  
  210.     public Token(String text) throws SyntaxError {
  211.         this(new Position(text));
  212.     }
  213.  
  214.     public String getValue () {
  215.         return Position.getSubstring(start, follow);
  216.     }
  217.  
  218.     private Token(Position cur) throws SyntaxError {
  219.         start = cur.skipWhile(Character::isWhitespace);
  220.         follow = start.skip();
  221.         switch (start.getChar()) {
  222.             case -1:
  223.                 tag = Tag.END_OF_TEXT;
  224.                 break;
  225.             case '(':
  226.                 tag = Tag.LBRACKET;
  227.                 break;
  228.             case ')':
  229.                 tag = Tag.RBRACKET;
  230.                 break;
  231.             case '=':
  232.                 tag = Tag.EQUALSIGN;
  233.                 break;
  234.             case '+':
  235.                 tag = Tag.PLUSSIGN;
  236.                 break;
  237.             case '-':
  238.                 tag = Tag.MINUSSIGN;
  239.                 break;
  240.             case ',':
  241.                 tag = Tag.COMMA;
  242.                 break;
  243.             case '*':
  244.                 tag = Tag.MULSIGN;
  245.                 break;
  246.             case '/':
  247.                 tag = Tag.DIVSIGN;
  248.                 break;
  249.             default:
  250.                 if (start.satisfies(Character::isLetter)) {
  251.                     follow =
  252. follow.skipWhile(Character::isLetterOrDigit);
  253.                     tag = Tag.IDENT;
  254.                 } else if (start.satisfies(Character::isDigit)) {
  255.                     follow = follow.skipWhile(Character::isDigit);
  256.                     if (follow.satisfies(Character::isLetter)) {
  257.                         throw new SyntaxError(follow, "delimiter
  258. expected");
  259.                     }
  260.                     tag = Tag.NUMBER;
  261.                 } else {
  262.                     throwError("invalid character");
  263.                 }
  264.         }
  265.     }
  266.  
  267.     public void throwError(String msg) throws SyntaxError {
  268.         throw new SyntaxError(start, msg);
  269.     }
  270.  
  271.     public boolean matches(Tag... tags) {
  272.         return Arrays.stream(tags).anyMatch(t -> tag == t);
  273.     }
  274.  
  275.     public Token next() throws SyntaxError {
  276.         return new Token(follow);
  277.     }
  278. }
  279.  
  280. class FormulaParser {
  281.  
  282.     private Token sym;
  283.     private Formula formula;
  284.     private HashSet<String> undefinedIdents;
  285.     private HashMap<String, Formula> providers;
  286.  
  287.     private int lcommas, rcommas;
  288.     private static int nextIdentifier = 0;
  289.  
  290.     private void expect(Tag tag) throws SyntaxError {
  291.         if (!sym.matches(tag)) {
  292.             sym.throwError(tag.toString() + " expected");
  293.         }
  294.         sym = sym.next();
  295.     }
  296.  
  297.     public FormulaParser(Formula formula, HashSet<String> undefs,
  298. HashMap<String, Formula> provs) throws SyntaxError {
  299.         providers = provs;
  300.         undefinedIdents = undefs;
  301.         this.formula = formula;
  302.         sym = new Token(formula.getFormula());
  303.     }
  304.  
  305.     // Используемая грамматика:
  306.     // <Formula> ::= <Vars> = <Exprs>
  307.     // <Vars> ::= IDENT <Vars'>.
  308.     // <Vars'> ::= , <Vars> | .
  309.     // <Exprs> ::= <Expr> <Exprs'>.
  310.     // <Exprs'> ::= , <Exprs> | .
  311.     // <Expr> ::= <Term> <Expr'> .
  312.     // <Expr'> ::= + <Term> <Expr'> | - <Term> <Expr'> | .
  313.     // <Term> ::= <Factor> <Term'>.
  314.     // <Term'> ::= * <Factor> <Term'> | / <Factor> <Term'> | .
  315.     // <Factor> ::= NUMBER | IDENT | ( <Expr> ) | - <Factor> .
  316.  
  317.     public void parse() throws SyntaxError {
  318.         parseFormula();
  319.         if (lcommas != rcommas)
  320.             sym.throwError("variables and expressions mismatch");
  321.         expect(Tag.END_OF_TEXT);
  322.     }
  323.  
  324.     private void parseFormula() throws SyntaxError {
  325.         parseVars();
  326.         expect(Tag.EQUALSIGN);
  327.         parseExprs();
  328.     }
  329.  
  330.     private void parseVars() throws SyntaxError {
  331.         if (sym.matches(Tag.IDENT)) {
  332.             String curIdent = sym.getValue();
  333.             undefinedIdents.remove(curIdent);
  334.             if (providers.containsKey(curIdent)) {
  335.                 sym.throwError("repeated definition of a variable");
  336.             } else {
  337.                 providers.put(curIdent, formula);
  338.             }
  339.         }
  340.         expect(Tag.IDENT);
  341.         parseVars_();
  342.     }
  343.  
  344.     private void parseVars_() throws SyntaxError {
  345.         if (sym.matches(Tag.COMMA)) {
  346.             expect(Tag.COMMA);
  347.             lcommas++;
  348.             parseVars();
  349.         }
  350.     }
  351.  
  352.     private void parseExprs() throws SyntaxError {
  353.         parseExpr();
  354.         parseExprs_();
  355.     }
  356.  
  357.     private void parseExprs_() throws SyntaxError {
  358.         if (sym.matches(Tag.COMMA)) {
  359.             expect(Tag.COMMA);
  360.             rcommas++;
  361.             parseExprs();
  362.         }
  363.     }
  364.  
  365.     private void parseExpr() throws SyntaxError {
  366.         parseTerm();
  367.         parseExpr_();
  368.     }
  369.  
  370.     private void parseExpr_() throws SyntaxError {
  371.         if (sym.matches(Tag.PLUSSIGN)) {
  372.             expect(Tag.PLUSSIGN);
  373.             parseTerm();
  374.             parseExpr_();
  375.         } else if (sym.matches(Tag.MINUSSIGN)) {
  376.             expect(Tag.MINUSSIGN);
  377.             parseTerm();
  378.             parseExpr_();
  379.         }
  380.     }
  381.  
  382.     private void parseTerm() throws SyntaxError {
  383.         parseFactor();
  384.         parseTerm_();
  385.     }
  386.  
  387.     private void parseTerm_() throws SyntaxError {
  388.         if (sym.matches(Tag.MULSIGN)) {
  389.             expect(Tag.MULSIGN);
  390.             parseFactor();
  391.             parseTerm_();
  392.         } else if (sym.matches(Tag.DIVSIGN)) {
  393.             expect(Tag.DIVSIGN);
  394.             parseFactor();
  395.             parseTerm_();
  396.         }
  397.     }
  398.  
  399.     private void parseFactor() throws SyntaxError {
  400.         if (sym.matches(Tag.NUMBER)) {
  401.             expect(Tag.NUMBER);
  402.         } else if (sym.matches(Tag.IDENT)) {
  403.             String curIdent = sym.getValue();
  404.             formula.addDependency(curIdent);
  405.             if (!providers.containsKey(curIdent)) {
  406.                 undefinedIdents.add(curIdent);
  407.             }
  408.             expect(Tag.IDENT);
  409.         } else if (sym.matches(Tag.LBRACKET)) {
  410.             expect(Tag.LBRACKET);
  411.             parseExpr();
  412.             expect(Tag.RBRACKET);
  413.         } else if (sym.matches(Tag.MINUSSIGN)) {
  414.             expect(Tag.MINUSSIGN);
  415.             parseFactor();
  416.         } else {
  417.             sym.throwError("identifier, number or expression expected");
  418.         }
  419.      }
  420.  
  421. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement