Expression Evaluation

Source

• lintcode: Expression Evaluation

Given an expression string array, return the final result of this expression

Example
For the expression 2*6-(23+7)/(1+2), input is

[
  "2", "*", "6", "-", "(",
  "23", "+", "7", ")", "/",
  (", "1", "+", "2", ")"
],
return 2

Note
The expression contains only integer, +, -, *, /, (, ).

题解

思路就是两个stack，一个存数字一个存符号。如果遇到数字直接存到数字stack；如果遇到符号，有几种情况：

1.当前符号比上一个符号优先级高，比如* 高于+，那么直接进栈

2.当前符号低于上一个，那么就要把所有已经在stack里面优先于当前符号的全算完，再推进当前符号

3.当前符号是“（”，直接push

4.当前符号是“）”，就要把所有“（”以前的符号全部算完

Java

public class Solution {
    /**
     * @param expression: an array of strings;
     * @return: an integer
     */
    public int evaluateExpression(String[] expression) {  
        // write your code here  
        Stack<Integer> intStack = new Stack<Integer>();  
        Stack<String> opStack = new Stack<String>();  

        int cur = 0;  
        while (cur < expression.length) {  
            String curStr = expression[cur];  
            if (isOp(curStr)) {  
                if (curStr.equals("(")) {  
                    opStack.push(curStr);  
                } else if (curStr.equals(")")) {  
                    while (!opStack.peek().equals("(")) {  
                        intStack.push(calc(intStack.pop(), intStack.pop(), opStack.pop()));  
                    }  
                    opStack.pop();  
                } else {  
                    while (!opStack.isEmpty() && precedence(curStr, opStack.peek())) {  
                        intStack.push(calc(intStack.pop(), intStack.pop(), opStack.pop()));  
                    }  
                    opStack.push(curStr);  
                }  
            } else {  
                intStack.push(Integer.valueOf(curStr));  
            }  
            cur++;  
        }  

        while (!opStack.isEmpty()) {  
            intStack.push(calc(intStack.pop(), intStack.pop(), opStack.pop()));  
        }  
        return intStack.isEmpty() ? 0 : intStack.pop();  
    }  

    int calc(int a, int b, String op) {  
        if (op.equals("+")) {  
            return a + b;  
        } else if (op.equals("-")) {  
            return b - a;  
        } else if (op.equals("*")) {  
            return a * b;  
        } else {  
            return b/a;  
        }  
    }  

    boolean isOp(String str) {  
        if (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")  
            || str.equals("(") || str.equals(")")) {  
            return true;  
        } else {  
            return false;  
        }  
    }  

    // if b takes precedence over a  
    boolean precedence(String a, String b) {  
        if (b.equals("*") || b.equals("/")) {  
            return true;  
        }  
        if (b.equals("+") || b.equals("-")) {  
            if(a.equals("*") || a.equals("/")) {  
                return false;  
            } else {  
                return true;  
            }  
        }  
        return false;  
    }  
};

Reference

Expression Evaluation