原题

求下方表达式的值

(1 + ((2 + 3) * (4 * 5)))

这道题在leetcode上有相似的题目逆波兰表达式求值

解题思路

我们可以通过双栈的方式来解这道题。

1. 遍历整个字符串，一个栈负责将操作数压入栈，另外一个栈负责将运算符压入栈。
2. 当遇到(时直接忽略，当遇到)时，对栈顶两个操作数进行运算。

代码

import java.util.Stack;

public class Evaluate {
    public static void main(String[] args) { 
        Stack<String> ops  = new Stack<String>();
        Stack<Double> vals = new Stack<Double>();
        String str = "(1 + ((2 + 3) * (4 * 5)))"
        for(String s: str) {
          if (s.equals("("));
          else if(s.equals("+")) ops.push(s);
          else if(s.equals("-")) ops.push(s);
          else if(s.equals("*")) ops.push(s);
          else if(s.equals("/")) ops.push(s);
          else if(s.equals(")")){
             Double v = vals.pop()
             String p = ops.pop()
             if     (p == "+")  v = vals.pop() + v;
             else if(p == "-")  v = vals.pop() - v;
             else if(p == "*")  v = vals.pop() * v;
             else if(p == "/")  v = vals.pop() / v;
          }
        }
            else vals.push(Double.parseDouble(s));
        }
        StdOut.println(vals.pop());
    }
}