Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.util.function.IntPredicate;
- public class FormulaOrder {
- private static int t = 1;
- private static void dfs (Formula f) {
- f.setT1(t++);
- f.setT2(-1);
- for (Formula e : f.getDependencies()) {
- if (e.getT1() == 0)
- dfs(e);
- if (e.getT2() == -1) {
- System.out.println("cycle");
- System.exit(1);
- }
- }
- f.setT2(t++);
- }
- public static void main (String[] args) {
- Scanner scn = new Scanner(System.in);
- HashSet<String> undefs = new HashSet<>();
- HashMap<String, Formula> fProviders = new HashMap<>();
- ArrayList<Formula> formulae = new ArrayList<>();
- while (scn.hasNextLine()) {
- Formula currentFormula = new Formula(scn.nextLine());
- formulae.add(currentFormula);
- try {
- FormulaParser fp = new FormulaParser(currentFormula,
- undefs, fProviders);
- fp.parse();
- }
- catch (SyntaxError se) {
- System.out.println("syntax error");
- System.exit(1);
- }
- }
- if (!undefs.isEmpty()) {
- System.out.println("syntax error");
- System.exit(1);
- }
- formulae.stream().forEach(f -> f.fetchDependencies(fProviders));
- for (Formula f : formulae) {
- if (f.getT1() == 0) {
- dfs(f);
- }
- }
- Collections.sort(formulae);
- for (Formula f : formulae)
- System.out.println(f);
- }
- }
- class Formula implements Comparable<Formula> {
- private String formula;
- private HashSet<String> dependsOn;
- private ArrayList<Formula> dependencies;
- private int T1, T2;
- public Formula(String formula) {
- this.formula = formula;
- dependsOn = new HashSet<>();
- dependencies = new ArrayList<>();
- }
- public String getFormula () {
- return formula;
- }
- public void fetchDependencies (HashMap<String, Formula> providers) {
- Iterator<String> dit = dependsOn.iterator();
- while (dit.hasNext()) {
- String curId = dit.next();
- Formula corrFormula = providers.get(curId);
- if (!dependencies.contains(corrFormula))
- dependencies.add(providers.get(curId));
- dit.remove();
- }
- }
- public void addDependency (String ident) {
- dependsOn.add(ident);
- }
- public ArrayList<Formula> getDependencies () {
- return dependencies;
- }
- public int compareTo (Formula other) {
- return Integer.compare(T2, other.T2);
- }
- public int getT2() {
- return T2;
- }
- public void setT2(int t2) {
- T2 = t2;
- }
- public int getT1() {
- return T1;
- }
- public void setT1(int t1) {
- T1 = t1;
- }
- @Override
- public String toString() {
- return formula;
- }
- }
- class Position {
- private String formula;
- private int index, line, col;
- public Position(String formula) {
- this(formula, 0, 1, 1);
- }
- private Position(String formula, int index, int line, int col) {
- this.formula = formula;
- this.index = index;
- this.line = line;
- this.col = col;
- }
- public int getChar() {
- return index < formula.length() ? formula.codePointAt(index) :
- -1;
- }
- public boolean satisfies(IntPredicate p) {
- return p.test(getChar());
- }
- public Position skip() {
- int c = getChar();
- switch (c) {
- case -1:
- return this;
- case '\n':
- return new Position(formula, index + 1, line + 1, 1);
- default:
- return new Position(formula, index + (c > 0xFFFF ? 2 :
- 1), line, col + 1);
- }
- }
- public static String getSubstring (Position start, Position follow)
- {
- return start.formula.substring(start.index, follow.index);
- }
- public Position skipWhile(IntPredicate p) {
- Position pos = this;
- while (pos.satisfies(p)) pos = pos.skip();
- return pos;
- }
- public String toString() {
- return String.format("(%d, %d)", line, col);
- }
- }
- class SyntaxError extends Exception {
- public SyntaxError(Position pos, String msg) {
- super(String.format("Syntax error at %s: %s", pos.toString(),
- msg));
- }
- }
- enum Tag {
- IDENT,
- NUMBER,
- EQUALSIGN,
- LBRACKET,
- RBRACKET,
- PLUSSIGN,
- MINUSSIGN,
- COMMA,
- MULSIGN,
- DIVSIGN,
- END_OF_TEXT
- }
- class Token {
- private Tag tag;
- private Position start, follow;
- public Token(String text) throws SyntaxError {
- this(new Position(text));
- }
- public String getValue () {
- return Position.getSubstring(start, follow);
- }
- private Token(Position cur) throws SyntaxError {
- start = cur.skipWhile(Character::isWhitespace);
- follow = start.skip();
- switch (start.getChar()) {
- case -1:
- tag = Tag.END_OF_TEXT;
- break;
- case '(':
- tag = Tag.LBRACKET;
- break;
- case ')':
- tag = Tag.RBRACKET;
- break;
- case '=':
- tag = Tag.EQUALSIGN;
- break;
- case '+':
- tag = Tag.PLUSSIGN;
- break;
- case '-':
- tag = Tag.MINUSSIGN;
- break;
- case ',':
- tag = Tag.COMMA;
- break;
- case '*':
- tag = Tag.MULSIGN;
- break;
- case '/':
- tag = Tag.DIVSIGN;
- break;
- default:
- if (start.satisfies(Character::isLetter)) {
- follow =
- follow.skipWhile(Character::isLetterOrDigit);
- tag = Tag.IDENT;
- } else if (start.satisfies(Character::isDigit)) {
- follow = follow.skipWhile(Character::isDigit);
- if (follow.satisfies(Character::isLetter)) {
- throw new SyntaxError(follow, "delimiter
- expected");
- }
- tag = Tag.NUMBER;
- } else {
- throwError("invalid character");
- }
- }
- }
- public void throwError(String msg) throws SyntaxError {
- throw new SyntaxError(start, msg);
- }
- public boolean matches(Tag... tags) {
- return Arrays.stream(tags).anyMatch(t -> tag == t);
- }
- public Token next() throws SyntaxError {
- return new Token(follow);
- }
- }
- class FormulaParser {
- private Token sym;
- private Formula formula;
- private HashSet<String> undefinedIdents;
- private HashMap<String, Formula> providers;
- private int lcommas, rcommas;
- private static int nextIdentifier = 0;
- private void expect(Tag tag) throws SyntaxError {
- if (!sym.matches(tag)) {
- sym.throwError(tag.toString() + " expected");
- }
- sym = sym.next();
- }
- public FormulaParser(Formula formula, HashSet<String> undefs,
- HashMap<String, Formula> provs) throws SyntaxError {
- providers = provs;
- undefinedIdents = undefs;
- this.formula = formula;
- sym = new Token(formula.getFormula());
- }
- // Используемая грамматика:
- // <Formula> ::= <Vars> = <Exprs>
- // <Vars> ::= IDENT <Vars'>.
- // <Vars'> ::= , <Vars> | .
- // <Exprs> ::= <Expr> <Exprs'>.
- // <Exprs'> ::= , <Exprs> | .
- // <Expr> ::= <Term> <Expr'> .
- // <Expr'> ::= + <Term> <Expr'> | - <Term> <Expr'> | .
- // <Term> ::= <Factor> <Term'>.
- // <Term'> ::= * <Factor> <Term'> | / <Factor> <Term'> | .
- // <Factor> ::= NUMBER | IDENT | ( <Expr> ) | - <Factor> .
- public void parse() throws SyntaxError {
- parseFormula();
- if (lcommas != rcommas)
- sym.throwError("variables and expressions mismatch");
- expect(Tag.END_OF_TEXT);
- }
- private void parseFormula() throws SyntaxError {
- parseVars();
- expect(Tag.EQUALSIGN);
- parseExprs();
- }
- private void parseVars() throws SyntaxError {
- if (sym.matches(Tag.IDENT)) {
- String curIdent = sym.getValue();
- undefinedIdents.remove(curIdent);
- if (providers.containsKey(curIdent)) {
- sym.throwError("repeated definition of a variable");
- } else {
- providers.put(curIdent, formula);
- }
- }
- expect(Tag.IDENT);
- parseVars_();
- }
- private void parseVars_() throws SyntaxError {
- if (sym.matches(Tag.COMMA)) {
- expect(Tag.COMMA);
- lcommas++;
- parseVars();
- }
- }
- private void parseExprs() throws SyntaxError {
- parseExpr();
- parseExprs_();
- }
- private void parseExprs_() throws SyntaxError {
- if (sym.matches(Tag.COMMA)) {
- expect(Tag.COMMA);
- rcommas++;
- parseExprs();
- }
- }
- private void parseExpr() throws SyntaxError {
- parseTerm();
- parseExpr_();
- }
- private void parseExpr_() throws SyntaxError {
- if (sym.matches(Tag.PLUSSIGN)) {
- expect(Tag.PLUSSIGN);
- parseTerm();
- parseExpr_();
- } else if (sym.matches(Tag.MINUSSIGN)) {
- expect(Tag.MINUSSIGN);
- parseTerm();
- parseExpr_();
- }
- }
- private void parseTerm() throws SyntaxError {
- parseFactor();
- parseTerm_();
- }
- private void parseTerm_() throws SyntaxError {
- if (sym.matches(Tag.MULSIGN)) {
- expect(Tag.MULSIGN);
- parseFactor();
- parseTerm_();
- } else if (sym.matches(Tag.DIVSIGN)) {
- expect(Tag.DIVSIGN);
- parseFactor();
- parseTerm_();
- }
- }
- private void parseFactor() throws SyntaxError {
- if (sym.matches(Tag.NUMBER)) {
- expect(Tag.NUMBER);
- } else if (sym.matches(Tag.IDENT)) {
- String curIdent = sym.getValue();
- formula.addDependency(curIdent);
- if (!providers.containsKey(curIdent)) {
- undefinedIdents.add(curIdent);
- }
- expect(Tag.IDENT);
- } else if (sym.matches(Tag.LBRACKET)) {
- expect(Tag.LBRACKET);
- parseExpr();
- expect(Tag.RBRACKET);
- } else if (sym.matches(Tag.MINUSSIGN)) {
- expect(Tag.MINUSSIGN);
- parseFactor();
- } else {
- sym.throwError("identifier, number or expression expected");
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement