Tuesday, February 10, 2015

LeetCode [150] Evaluate Reverse Polish Notation

 150. Evaluate Reverse Polish Notation

Medium

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +-*/. Each operand may be an integer or another expression.

Note:

  • Division between two integers should truncate toward zero.
  • The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation.

Example 1:

Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Explanation: 
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> stk;
        int n = tokens.size();
        for(int i=0; i<n; ++i){
            string s = tokens[i];
            if(s=="+"||s=="-"||s=="*"||s=="/"){
                int rhs = stk.top();
                stk.pop();
                int lhs = stk.top();
                stk.pop();
                int res;
                if(s=="+") res = lhs+rhs;
                else if(s=="-") res = lhs-rhs;
                else if(s=="*") res = lhs*rhs;
                else if(s=="/")  res = lhs/rhs;
                stk.push(res);
            }else{
                stk.push(stoi(s));
            }
        }
        return stk.top();
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stk = new Stack<>();
        for(String s : tokens){
            if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")){
                int b = stk.pop();
                int a = stk.pop();
                int r = 0;
                if(s.equals("+")) r = a+b;
                else if(s.equals("-")) r = a-b;
                else if(s.equals("*")) r = a*b;
                else r=a/b;
                stk.add(r);
            }else{
                stk.push(Integer.parseInt(s));
            }
        }
        return stk.pop();
    }
}

No comments:

Post a Comment