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.

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

 

解题:

          逆波兰表示法Reverse Polish notationRPN,或逆波兰记法),将操作数放到操作符前的一种数学表达式方式,也被称作后缀表示法。

         1. 使用栈: 针对本题由于操作符指定为二元运算,具体操作有流程有所简化, 遇到操作数入栈, 遇到操作符,将两个操作数出栈,进行运算,将结果再次入栈,以此类推,知道完成所有数组的遍历,栈顶指针即为结果。

实现:

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> ss;
        if (tokens.size() == 1) { 
            return stoi(tokens[0]);
        } 
        for (auto s:tokens){            
            if (s !="+" && s !="-" && s!="*" && s!="/" ){
                ss.push(stoi(s));
            }
            else{
                int num2 = ss.top();
                ss.pop();
                int num1 = ss.top();
                ss.pop();
                
                int result;
                switch (s[0]){
                    case '+':
                        result = num1+num2;
                        break;
                    case '-':
                        result = num1-num2;
                        break;
                    case '*':
                        result = num1*num2;
                        break;
                    case '/':
                        if (num2 == 0){
                            result = 0;
                        }else {
                            result = num1/num2;
                        }
                        break;
                    default:
                        result = 0;
                        break;
                }
               
                ss.push(result);
            }
        }
             
        return ss.top();
    }
};

             2. 递归 从数组末尾开始调用,如果遇到操作符,继续向前递归调用,找到对应的两个数字后,进行运算返回结果; 如果遇到数字,直接返回。

 

实现:

int evalRPN(vector<string>& tokens) {
    auto t = tokens.back(); tokens.pop_back();
    if (isdigit(t.back())) return stoi(t);
    int n2 = evalRPN(tokens), n1 = evalRPN(tokens);
    return t[0] == '+' ? n1 + n2 : t[0] == '-' ? n1 - n2 : t[0] == '*' ? n1 * n2 : n1 / n2;
}

 

参考:

[LeetCode] Evaluate Reverse Polish Notation 计算逆波兰表达式

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注