By

文章目录
  1. 1. Evaluate Reverse Polish Notation
    1. 1.1. 题目
    2. 1.2. 思路
    3. 1.3. 解题

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

思路

逆波兰表达式计算，遇到数入栈，遇到运算符，出栈两元素进行运算，得到运算结果将运算结果入栈。字符串转换成数的问题，考虑负数情况。

解题

c++版

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
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> cache;  
        for(int i = 0 ; i < tokens.size(); i++){  
            if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"){  
                int num2 = cache.top();  
                cache.pop();  
                int num1 = cache.top();  
                cache.pop();  
                cache.push(calculate(num1, num2, tokens[i]));  
            }  
            else{  
                cache.push(str2int(tokens[i]));  
            }  
        }  
        return cache.top();  
    }
    
    int str2int(string s){  
        int result=0;  
        int base=1;  
        for(int i = s.size()-1;i>=0;i--){  
            if(s[i] == '-' && i == 0){  
                result *= -1;  
            }  
            else if(s[i] >= '0' && s[i] <= '9'){  
                result += base * (s[i] - '0');  
                base *= 10;  
            }  
        }  
        return result;  
    }  
      
    int calculate(int num1, int num2, string op){  
        if(op == "+"){  
            return num1 + num2;  
        }  
        else if(op == "-"){  
            return num1 - num2;  
        }  
        else if(op == "*"){  
            return num1 * num2;  
        }else if(op == "/"){  
            return num1 / num2;  
        }  
    }  
};

python版

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
37
class Solution:
    # @param {string[]} tokens
    # @return {integer}
    def evalRPN(self, tokens):
        s=[]
        for i in range(len(tokens)):
            if tokens[i] == "+" or tokens[i] == "-" or tokens[i] == "*" or tokens[i] == "/":
                num2=s.pop()
                num1=s.pop()
                s.append(self.calculate(num1,num2,tokens[i]))
            else:
                s.append(self.str2int(tokens[i]))
        return s.pop()

    
    def calculate(self,num1,num2,operator):
        if operator=="+":
            return num1+num2;
        elif operator=="-":
            return num1-num2;
        elif operator=="*":
            return num1*num2;
        elif operator=="/":
            if num1*num2<0:
                return -((-num1)/num2)
            return num1/num2;
            
    def str2int(self,string):
        result=0
        base=1
        for i in range(len(string)-1,-1,-1):
            if string[i]=='-' and i==0:
                result*=-1
            elif string[i]>='0' and string[i]<='9':
                result+=base*int(string[i])
                base*=10
        return result

leetcode
leetcode,stack
文章目录
  1. 1. Evaluate Reverse Polish Notation
    1. 1.1. 题目
    2. 1.2. 思路
    3. 1.3. 解题