Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Arrays;
- import java.util.ArrayList;
- import java.util.HashMap;
- import java.util.Scanner;
- public class FormulaOrder {
- private static String ops = "+-*/(),=";
- private static HashMap<String, Integer> dict = new HashMap<>();
- private static ArrayList<Formula> forms = new ArrayList<>();
- private static ArrayList<Integer> order = new ArrayList<>();
- private static void dfs(int n){
- forms.get(n).color = 1;
- for (int i = 0; i < forms.get(n).to.size(); i++) {
- int to = forms.get(n).to.get(i);
- if(forms.get(to).color != 2){
- if(forms.get(to).color == 1){
- System.out.print("cycle");
- System.exit(0);
- } else{
- dfs(to);
- }
- }
- }
- order.add(n);
- forms.get(n).color = 2;
- }
- public static void main(String[] args){
- Scanner in = new Scanner(System.in);
- while(in.hasNext()){
- forms.add(new Formula(in.nextLine()));
- }
- for(int i = 0; i < forms.size(); i++){
- for (String var : forms.get(i).vars) {
- if(!dict.containsKey(var)) dict.put(var, i);
- else error();
- }
- }
- for(int i = 0; i < forms.size(); i++){
- for (String subvar : forms.get(i).subvars) {
- if(dict.containsKey(subvar)) forms.get(i).to.add(dict.get(subvar));
- else error();
- }
- }
- for(int i = 0; i < forms.size(); i++){
- if(forms.get(i).color == 0) dfs(i);
- }
- for (int i : order) {
- System.out.println(forms.get(i).form);
- }
- }
- private static void error(){
- System.out.println("syntax error");
- System.exit(0);
- }
- private static class Formula{
- String form;
- ArrayList<Token> tokens;
- ArrayList<String> vars, subvars;
- ArrayList<Integer> to;
- int color, current, formCount;
- public Formula(String form){
- this.form = form;
- vars = new ArrayList<>();
- subvars = new ArrayList<>();
- to = new ArrayList<>();
- tokens = new ArrayList<>();
- color = 0;
- formCount = 0;
- lexer();
- parseFormula();
- if(current != tokens.size() - 1 || formCount != vars.size()) error();
- }
- private void lexer(){
- current = 0;
- do{
- if(form.charAt(current) == ' '){
- current++;
- continue;
- }
- if(ops.contains(Character.toString(form.charAt(current)))){
- tokens.add(new Token(1, Character.toString(form.charAt(current))));
- }else if(Character.isDigit(form.charAt(current))){
- tokens.add(new Token(0, getNumber()));
- }else if(Character.isAlphabetic(form.charAt(current))){
- tokens.add(new Token(2, getId()));
- }else error();
- current++;
- }while(current < form.length());
- }
- private String getId(){
- int begin = current;
- while(current + 1 < form.length() && (Character.isAlphabetic(form.charAt(current + 1)) || Character.isDigit(form.charAt(current + 1)))){
- current++;
- }
- return form.substring(begin, current+1);
- }
- private String getNumber(){
- int begin = current;
- while(current + 1 < form.length() && Character.isDigit(form.charAt(current + 1))){
- current++;
- }
- return form.substring(begin, current+1);
- }
- private void parseFormula(){
- current = 0;
- parseIdents();
- if(peek().name.equals("=")){
- current+=2;
- parseExprs();
- } else error();
- }
- private void parseIdents(){
- if(current >= tokens.size()) error();
- if(tokens.get(current).type == 2) vars.add(tokens.get(current).name); else error();
- if (peek().name.equals(",")){
- current+=2;
- parseIdents();
- }
- }
- private void parseExprs(){
- formCount++;
- if(current >= tokens.size()) error();
- parseE();
- if (peek().name.equals(",")){
- current+=2;
- parseExprs();
- }
- }
- private void parseE(){
- if(current >= tokens.size()) error();
- parseT();
- if(peek().name.equals("+") || peek().name.equals("-")){
- current+=2;
- parseE2();
- }
- }
- private void parseE2(){
- if(current >= tokens.size()) error();
- parseT();
- if(peek().name.equals("+") || peek().name.equals("-")){
- current+=2;
- parseE2();
- }
- }
- private void parseT(){
- if(current >= tokens.size()) error();
- parseF();
- if(peek().name.equals("*") || peek().name.equals("/")){
- current+=2;
- parseT2();
- }
- }
- private void parseT2(){
- if(current >= tokens.size()) error();
- parseF();
- if(peek().name.equals("*") || peek().name.equals("/")){
- current+=2;
- parseT2();
- }
- }
- private void parseF(){
- if(current >= tokens.size()) error();
- if(tokens.get(current).type == 0){
- }else if(tokens.get(current).type == 2){
- subvars.add(tokens.get(current).name);
- }else if(tokens.get(current).name.equals("(")){
- current++;
- parseE();
- if (peek().name.equals(")")) current++;
- else error();
- }else if(tokens.get(current).name.equals("-")){
- current++;
- parseF();
- }else error();
- }
- private Token peek(){
- if(current+1 < tokens.size()) return tokens.get(current+1);
- return new Token();
- }
- private class Token{
- int type;
- String name;
- int value;
- private Token(int type, String value){
- this.type = type;
- if(type == 0){
- this.value = Integer.parseInt(value);
- this.name = "";
- }
- else this.name = value;
- }
- private Token(){
- type = -1;
- name = "";
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement