API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Apr 30th, 2016
67
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 9.03 KB | None | 0 0
raw download clone embed print report
  1. import java.util.*;
  2.  
  3. public class Modules {
  4. static Vertex[] graph;
  5. static int position;
  6. static HashMap<String, Vertex> functions;
  7. static Stack<Vertex> stack;
  8. static int time = 1, count = 1;
  9. public static void main(String[] args) {
  10. Scanner in = new Scanner(System.in);
  11. ArrayList<String> expr = new ArrayList<>();
  12. while (in.hasNextLine()) expr.add(in.nextLine());
  13. int length = expr.size();
  14. for (int i = 0; i < length; i++)
  15. if (expr.get(i).length() == 0)
  16. expr.remove(i);
  17. length = expr.size();
  18. ArrayList<Token>[] Lex = new ArrayList[length];
  19. graph = new Vertex[length];
  20. functions = new HashMap<>();
  21. stack = new Stack<>();
  22. for (int i = 0; i < length; i++) {
  23. Lex[i] = new ArrayList<>();
  24. getTokens(expr.get(i), Lex[i]);
  25. graph[i] = new Vertex(Lex[i], expr.get(i));
  26. }
  27. Program();
  28. }
  29.  
  30. static class Vertex {
  31. ArrayList<Token> value;
  32. ArrayList<Vertex> next;
  33. ArrayList<String> vars;
  34. String name;
  35. String formula;
  36. int need;
  37. int t1, comp, low;
  38. public Vertex(ArrayList<Token> v, String f) {
  39. this.value = v;
  40. this.formula = f;
  41. next = new ArrayList<>();
  42. this.vars = new ArrayList<>();
  43. need = 0;
  44. }
  45. }
  46. static void visitVertex(Vertex v) {
  47. v.t1 = v.low = time++;
  48. stack.push(v);
  49. Vertex temp;
  50. for (Vertex u : v.next) {
  51. if (u.t1 == 0) visitVertex(u);
  52. if (u.comp == 0 && v.low > u.low) v.low = u.low;
  53. }
  54. if (v.t1 == v.low) {
  55. do {
  56. temp = stack.pop();
  57. temp.comp = count;
  58. } while (temp != v);
  59. count++;
  60. }
  61. }
  62. public static void ERROR(){
  63. System.out.print("error");
  64. System.exit(0);
  65. }
  66. private static void MakeFuncGraph(Vertex[] graph) {
  67. for (Vertex v : graph) {
  68. functions.put(v.value.get(0).value, v);
  69. for (Token item : v.value) {
  70. if (item.matches(Tag.IDENT)) v.need++;
  71. if (item.matches(Tag.EQ)) break;
  72. }
  73. v.need--;
  74. }
  75. for (Vertex item : graph) {
  76. position = 0;
  77. try {
  78. parseFunc(item);
  79. } catch (Exception e) {
  80. ERROR();
  81. }
  82. if (position < item.value.size()) ERROR();
  83. }
  84. }
  85. static void Program (){
  86. MakeFuncGraph(graph);
  87. for (Vertex v : graph) {
  88. if (v.t1 == 0) {
  89. visitVertex(v);
  90. }
  91. }
  92. System.out.print(--count);
  93. }
  94.  
  95. private static void getTokens(String exp, ArrayList<Token> Lex) {
  96. int i, j, length = exp.length();
  97. for (i = 0; i < length; i++) {
  98. char k = exp.charAt(i);
  99. if (exp.charAt(i) != ' ') {
  100. if (exp.charAt(i) == '+') Lex.add(new Token("+", Tag.PLUS));
  101. else if (k == '-') Lex.add(new Token("-", Tag.SUB));
  102. else if (k == '*') Lex.add(new Token("*", Tag.MUL));
  103. else if (k == '/') Lex.add(new Token("/", Tag.DIV));
  104. else if (k == '=') Lex.add(new Token("=", Tag.EQ));
  105. else if (k == '(') Lex.add(new Token("(", Tag.OPEN));
  106. else if (k == ')') Lex.add(new Token(")", Tag.CLOSE));
  107. else if (k == ',') Lex.add(new Token(",", Tag.COMMA));
  108. else if (k == ':') Lex.add(new Token(",", Tag.DOUBLEP));
  109. else if (k == ';') Lex.add(new Token(";", Tag.EOFUNC));
  110. else if (k == '?') Lex.add(new Token(";", Tag.QUEST));
  111. else if (k == '<') Lex.add(new Token("<", Tag.LEFT));
  112. else if (k == '>') Lex.add(new Token("<", Tag.RIGHT));
  113. else if (Character.isDigit(k)) {
  114. j=i;
  115. while (j < length && Character.isDigit(exp.charAt(j))) {
  116. j++;
  117. }
  118. Lex.add(new Token(exp.substring(i, j), Tag.NUM));
  119. i = --j;
  120. } else if (Character.isLetter(k)) {
  121. j=i;
  122. while (j < length && (Character.isDigit(exp.charAt(j)) || Character.isLetter(exp.charAt(j)))){
  123. j++;
  124. }
  125. Lex.add(new Token(exp.substring(i, j), Tag.IDENT));
  126. i = --j;
  127. } else ERROR();
  128. }
  129. }
  130. }
  131. enum Tag {
  132. PLUS, DIV, MUL, SUB, EQ, OPEN, CLOSE, COMMA, NUM, IDENT, DOUBLEP, EOFUNC, QUEST, LEFT, RIGHT
  133. }
  134. static class Token {
  135. String value;
  136. Tag tag;
  137. public Token(String value, Tag tag) {
  138. this.tag = tag;
  139. this.value = value;
  140. }
  141. public boolean matches(Tag... tags) {
  142. return Arrays.stream(tags).anyMatch(t -> tag == t);
  143. }
  144. }
  145.  
  146.  
  147. private static void parseFunc(Vertex v) {
  148. if (v.value.get(position).tag != Tag.IDENT && v.value.get(position + 1).tag != Tag.OPEN) ERROR();
  149. v.name = v.value.get(position).value;
  150. position += 2;
  151. parseFormalArgsList(v);
  152. if (v.value.get(position).tag != Tag.CLOSE || v.value.get(position + 1).tag != Tag.DOUBLEP || v.value.get(position + 2).tag != Tag.EQ) ERROR();
  153. position += 3;
  154. parseExpr(v);
  155. if (v.value.get(position).tag != Tag.EOFUNC) ERROR();
  156. position++;
  157. }
  158. private static void parseFormalArgsList(Vertex v){
  159. if(v.value.get(position).tag==Tag.CLOSE) return;
  160. parseIdentList(v);
  161. }
  162. private static void parseIdentList(Vertex v){
  163. if(v.value.get(position).tag!=Tag.IDENT) ERROR();
  164. v.vars.add(v.value.get(position).value);
  165. position++;
  166. while(v.value.get(position).tag==Tag.COMMA){
  167. position++;
  168. parseIdentList(v);
  169. }
  170. }
  171. private static void parseExpr(Vertex v){
  172. parseCompExpr(v);
  173. if(v.value.get(position).tag==Tag.QUEST){
  174. position++;
  175. parseCompExpr(v);
  176. if(v.value.get(position).tag!=Tag.DOUBLEP) ERROR();
  177. position++;
  178. parseExpr(v);
  179. }
  180. }
  181. private static void parseCompExpr(Vertex v){
  182. parseArithExpr(v);
  183. if(v.value.get(position).tag==Tag.EQ){
  184. position++;
  185. parseArithExpr(v);
  186. }
  187. if(v.value.get(position).tag==Tag.LEFT){
  188. position++;
  189. if(v.value.get(position).tag==Tag.RIGHT || v.value.get(position).tag==Tag.EQ) position++;
  190. parseArithExpr(v);
  191. }
  192. if(v.value.get(position).tag==Tag.RIGHT){
  193. position++;
  194. if(v.value.get(position).tag==Tag.EQ) position++;
  195. parseArithExpr(v);
  196. }
  197. }
  198. private static void parseArithExpr(Vertex v){
  199. parseF(v);
  200. while(position<v.value.size()&&(v.value.get(position).tag==Tag.MUL || v.value.get(position).tag==Tag.DIV)) {
  201. position++;
  202. parseF(v);
  203. }
  204. while(position<v.value.size()&&(v.value.get(position).tag == Tag.PLUS || v.value.get(position).tag == Tag.SUB)){
  205. position++;
  206. parseF(v);
  207. while(position<v.value.size()&&(v.value.get(position).tag==Tag.MUL || v.value.get(position).tag==Tag.DIV)) {
  208. position++;
  209. parseF(v);
  210. }
  211. }
  212. }
  213. private static void parseF(Vertex v){
  214. if(v.value.get(position).tag == Tag.NUM) position++;
  215. else if(v.value.get(position).tag == Tag.IDENT){
  216. if(v.value.get(position+1).tag==Tag.OPEN){
  217. String name = v.value.get(position).value;
  218. position+=2;
  219. int given = parseActArgList(v);
  220. if(v.value.get(position).tag!=Tag.CLOSE) ERROR();
  221. if(!functions.containsKey(name) || functions.get(name).need!=given) ERROR();
  222. if(!v.next.contains(functions.get(name)) && v!=functions.get(name))v.next.add(functions.get(name));
  223. }
  224. else if(!v.vars.contains(v.value.get(position).value)) ERROR();
  225. position++;
  226. }
  227. else if(v.value.get(position).tag == Tag.OPEN){
  228. position++;
  229. parseExpr(v);
  230. if(v.value.get(position).tag!=Tag.CLOSE) ERROR();
  231. position++;
  232. }
  233. else if(v.value.get(position).tag == Tag.SUB){
  234. while(v.value.get(position).tag == Tag.SUB) position++;
  235. parseF(v);
  236. }
  237. else ERROR();
  238. }
  239. private static int parseActArgList(Vertex v){
  240. int res=0;
  241. if(v.value.get(position).tag==Tag.CLOSE) return 0;
  242. parseExpr(v);
  243. while(v.value.get(position).tag==Tag.COMMA){
  244. position++;
  245. parseExpr(v);
  246. res++;
  247. }
  248. return (++res);
  249. }
  250. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!