Wednesday, November 19, 2014

[LeetCode] Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +-*/. Each operand may be an integer or another expression.
Some examples:
  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6


思路:

典型的stack问题。逐一扫描每个token,如果是数字,则push入stack,如果是运算符,则从stack中pop出两个数字,进行运算,将结果push回stack。最后留在stack里的数即为最终结果。

以题中例子说明

exp:     2    1      +    3      *
stack:   2    2,1   3    3,3   9


 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
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    int evalRPN(vector<string> &tokens) {
        stack<int> s;
        for(int i=0; i<tokens.size(); i++) {
            if(isOp(tokens[i])) {
                int y = s.top();
                s.pop();
                int x = s.top();
                s.pop();
                s.push(evaluate(x, y, tokens[i]));
            }
            else {
                s.push(stoi(tokens[i], nullptr, 10));
                //s.push(atoi(tokens[i].c_str()));
            }
        }
        return s.top();
    }
    
    bool isOp(string s) {
        if(s=="+" || s=="-" || s=="*" || s=="/") return true;
        return false;
    }
    
    int evaluate(int x, int y, string op) {
        if(op=="+")
            return x+y;
        else if(op=="-")
            return x-y;
        else if(op=="*")
            return x*y;
        else if(op=="/")
            return x/y;
    }
};


总结:

1. 易犯的错误是将参与运算的两个数的顺序搞反。要计算 x op y,y是后压入的数,所以也是先被pop出来的数。第二次pop的时候才得到x的值。

2. 要注意stoi和atoi两个库函数的不同用法。

No comments:

Post a Comment