java

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
/**
* Created by sher on 19.04.15.
*/
import java.util.*;
class Parser {
public static Map<String, Integer> vars = new Hashtable<>();
public List<String> depends = new ArrayList<>();
public String name;
public int n;
private Deque<String> lexems;
int mark = 1;
public List<Parser> edges = new ArrayList<>();
Parser(Deque<String> y, int n, String name) {
lexems = y;
this.n = n;
this.name = name;
}
public void parse() throws Exception {
int x = parseVars();
if (x < 1) {
throw new RuntimeException();
}
while (lexems.size() != 0) {
parseExpr();
String lx = lexems.poll();
if (lx != null && (!lx.equals(",") || lexems.size() == 0)) {
throw new RuntimeException();
}
x--;
}
if (x != 0) {
throw new RuntimeException();
}
}
private int parseVars() {
String lx;
int ans = 0;
if (!Character.isLetter((lx = lexems.poll()).charAt(0))) {
throw new RuntimeException();
}
while (!lx.equals("=")) {
if (Character.isLetter(lx.charAt(0))) {
if (vars.put(lx, n) != null) {
throw new RuntimeException();
}
ans++;
} else if (lx.equals(",") && Character.isLetter(lexems.peek().charAt(0))) {
} else {
throw new RuntimeException();
}
lx = lexems.poll();
}
return ans;
}
private void parseExpr() throws Exception {
parseTerm();
for (; lexems.size() != 0 && (lexems.peek().equals("+") || lexems.peek().equals("-")); ) {
lexems.poll();
parseTerm();
}
}
private void parseTerm() throws Exception {
parsePower();
for (; lexems.size() != 0 && (lexems.peek().equals("*") || lexems.peek().equals("/")); ) {
lexems.poll();
parsePower();
}
}
private void parsePower() throws Exception {
String lx = lexems.poll();
if (Character.isDigit(lx.charAt(0)))
return;
else if (Character.isLetter(lx.charAt(0)))
depends.add(lx);
else if (lx.equals("-"))
parsePower();
else if (lx.equals("(")) {
parseExpr();
if (!lexems.poll().equals(")"))
throw new Exception("Expected ')'");
} else
throw new Exception("Bad lexem: " + lx);
}
public String toString() { return name; }
}
public class FormulaOrder {
private static Map<String, Integer> vars = new Hashtable<>();
private static Scanner in = new Scanner(System.in);
private static Deque<String> lexer(String expr) {
Deque<String> lexems = new ArrayDeque<>();
for (int i = 0; i < expr.length(); i++) {
char c = expr.charAt(i);
if (c == ' ')
continue;
else if (Character.isLetterOrDigit(c)) {
String token = new String();
for (; Character.isLetterOrDigit(c); i++, c = expr.charAt(i)) { token += (c + ""); }
lexems.add(token);
i--;
} else
lexems.add(Character.toString(c));
}
return lexems;
}
static void dfs(Parser v, List<Parser> ans) {
v.mark = 0;
for (Parser u : v.edges) {
if (u.mark == 0) {
System.out.println("cycle");
System.exit(0);
} else if (u.mark == 1) {
dfs(u, ans);
}
}
v.mark = -1;
ans.add(v);
}
public static void main(String args[]) {
List<Parser> g = new ArrayList<>();
int i;
for (i = 0; in.hasNextLine(); i++) {
String expr = in.nextLine() + " ";
Deque<String> lexems = lexer(expr);
g.add(new Parser(lexems, i, expr));
vars.put(expr.split("=")[0], i);
try {
g.get(g.size() - 1).parse();
} catch (Exception e) {
System.out.print("syntax error");
System.exit(0);
}
}
try {
for (Parser x : g) {
// System.out.print(x + " : ");
for (String y : x.depends) {
x.edges.add(g.get(Parser.vars.get(y)));
}
// System.out.println(x.depends);
}
} catch (Exception r) {
System.out.println("syntax error");
System.exit(0);
}
List<Parser> ans = new ArrayList<>();
for (Parser v : g) {
if (v.mark == 1) {
dfs(v, ans);
}
}
for (Parser a : ans) {
System.out.println(a);
}
}
// public void dfs()
}