java - Dijkstra's two-stack algorithm for expression evaluation -

i'm reading book on algorithms , data structures , try follow examples. try implement dijkstra's two-stack algorithm expression evaluation. takes input in form of string ( 1 + 2 ) * 3 , evaluates expression. code compiles doesn't produce correct output.

the output above expression is:

3.0 

here's code:

public class eval {     public static void main(string[] args) {         string s = "( 1 + 2 ) * 3";         evaluateandprintresult(s);     }     public static void evaluateandprintresult(string s)     {         string[] str = s.split("\\s+");         queue<string> q = new linkedlist<string>();         for(string ss : str)             q.add(ss);         stack<string> ops = new stack<string>();         stack<double> vals = new stack<double>();         while (!q.isempty())         { // read token, push if operator.             string token = q.poll();             if (token.equals("(")) ;             else if (token.equals("+")) ops.push(s);             else if (token.equals("-")) ops.push(s);             else if (token.equals("*")) ops.push(s);             else if (token.equals("/")) ops.push(s);             else if (token.equals("sqrt")) ops.push(s);             else if (token.equals(")"))             { // pop, evaluate, , push result if token ")".                 string op = ops.pop();                 double v = vals.pop();                 if (op.equals("+")) v = vals.pop() + v;                 else if (op.equals("-")) v = vals.pop() - v;                 else if (op.equals("*")) v = vals.pop() * v;                 else if (op.equals("/")) v = vals.pop() / v;                 else if (op.equals("sqrt")) v = math.sqrt(v);                 vals.push(v);             } // token not operator or paren: push double value.             else vals.push(double.parsedouble(token));         }         system.out.println(vals.pop());     } }    

i don't understand program enough correct it. how can correct program?

your problem in several places use ops.push(s). should using ops.push(token).

you pushing whole expression, should push current token.

this code correctly prints 9.0.

public static void evaluateandprintresult(string s) {     string[] str = s.split("\\s+");     queue<string> q = new linkedlist<>();     q.addall(arrays.aslist(str));     stack<string> ops = new stack<>();     stack<double> vals = new stack<>();     while (!q.isempty()) { // read token, push if operator.         string token = q.poll();         if (token.equals("(")) {         } else if (token.equals("+")) {             ops.push(token);         } else if (token.equals("-")) {             ops.push(token);         } else if (token.equals("*")) {             ops.push(token);         } else if (token.equals("/")) {             ops.push(token);         } else if (token.equals("sqrt")) {             ops.push(token);         } else if (token.equals(")")) { // pop, evaluate, , push result if token ")".             // replace top exp it' result.             double v = vals.pop();             string op = ops.pop();             if (op.equals("+")) {                 v = vals.pop() + v;             } else if (op.equals("-")) {                 v = vals.pop() - v;             } else if (op.equals("*")) {                 v = vals.pop() * v;             } else if (op.equals("/")) {                 v = vals.pop() / v;             } else if (op.equals("sqrt")) {                 v = math.sqrt(v);             }             vals.push(v);         } else {             // token not operator or paren: push double value.             vals.push(double.parsedouble(token));         }     }     system.out.println(vals.pop()); }  public void test() {     evaluateandprintresult("( ( 1 + 2 ) * 3 )"); } 

however, expression "( 1 + 2 ) * 3" still evaluates 3.0. solve need evaluate last op pushed, if there one.

public static void evaluateandprintresult(string s) {     string[] str = s.split("\\s+");     queue<string> q = new linkedlist<>();     q.addall(arrays.aslist(str));     stack<string> ops = new stack<>();     stack<double> vals = new stack<>();     while (!q.isempty()) { // read token, push if operator.         string token = q.poll();         if (token.equals("(")) {         } else if (token.equals("+")) {             ops.push(token);         } else if (token.equals("-")) {             ops.push(token);         } else if (token.equals("*")) {             ops.push(token);         } else if (token.equals("/")) {             ops.push(token);         } else if (token.equals("sqrt")) {             ops.push(token);         } else if (token.equals(")")) {             vals.push(evaluateop(ops, vals));         } else {             // token not operator or paren: push double value.             vals.push(double.parsedouble(token));         }     }     system.out.println(evaluateop(ops, vals)); }  private static double evaluateop(stack<string> ops, stack<double> vals) {     // replace top exp result.     double v = vals.pop();     string op = ops.pop();     if (op.equals("+")) {         v = vals.pop() + v;     } else if (op.equals("-")) {         v = vals.pop() - v;     } else if (op.equals("*")) {         v = vals.pop() * v;     } else if (op.equals("/")) {         v = vals.pop() / v;     } else if (op.equals("sqrt")) {         v = math.sqrt(v);     }     return v; }  public void test() {     evaluateandprintresult("( 1 + 2 ) * 3"); } 

and - tidier way of doing it.

public static void evaluateandprintresult(string s) {     string[] str = s.split("\\s+");     queue<string> q = new linkedlist<>();     q.addall(arrays.aslist(str));     stack<string> ops = new stack<>();     stack<double> vals = new stack<>();     while (!q.isempty()) { // read token, push if operator.         string token = q.poll();         switch (token) {             case "(":                 break;             case "+":             case "-":             case "*":             case "/":             case "sqrt":                 ops.push(token);                 break;             case ")":                 vals.push(evaluateop(ops, vals));                 break;             default:                 // token not operator or paren: push double value.                 vals.push(double.parsedouble(token));                 break;         }     }     system.out.println(s + " = " + evaluateop(ops, vals)); }  private static double evaluateop(stack<string> ops, stack<double> vals) {     // replace top exp result.     double v = vals.pop();     if (!ops.empty()) {         string op = ops.pop();         switch (op) {             case "+":                 v = vals.pop() + v;                 break;             case "-":                 v = vals.pop() - v;                 break;             case "*":                 v = vals.pop() * v;                 break;             case "/":                 v = vals.pop() / v;                 break;             case "sqrt":                 v = math.sqrt(v);                 break;             default:                 break;         }     }     return v; }  public void test() {     evaluateandprintresult("( ( 1 + 2 ) * 3 )"); }