Leetcode: Evaluate Reverse Polish Notation

迷南。 2022-08-05 14:28 4阅读 0赞

题目：  
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

分析：  
所谓的逆波兰表达式就是后缀表达式，参见我的另一篇博客：[计算器：中缀表达式转后缀表达式 ][Link 1]  
这道题的解法同样是利用栈，遇到数字压栈，遇到运算符栈顶两个数字进行运算，结果压栈，最后返回栈顶数字即可。

C++代码：

class Solution
    {
    public:
        int evalRPN(vector<string> &tokens)
        {
            stack<int> operands;
            size_t size = tokens.size();
            int operandX, operandY;
            int result;
            for (size_t i = 0; i < size; i++)
            {
                if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")
                {
                    operandY = operands.top();
                    operands.pop();
                    operandX = operands.top();
                    operands.pop();
                    //C++的switch语句不支持string类型
                    switch (tokens[i][0])
                    {
                        case '+':
                            result = operandX + operandY;
                            break;
                        case '-':
                            result = operandX - operandY;
                            break;
                        case '*':
                            result = operandX * operandY;
                            break;
                        case '/':
                            result = operandX / operandY;
                            break;
                        default:
                            break;
                    }
                    operands.push(result);
                }
                else
                {
                    operands.push(atoi(tokens[i].c_str()));
                }
            }
            return operands.top();
        }
    };

C\#代码：

public class Solution
    {
        public int EvalRPN(string[] tokens)
        {
            Stack<int> operands = new Stack<int>();
            int operandX, operandY;
            int result = 0;
            foreach (string item in tokens)
            {
                if (item == "+" || item == "-" || item == "*" || item == "/")
                {
                    operandY = operands.Pop();
                    operandX = operands.Pop();
                    switch (item)
                    {
                        case "+":
                            result = operandX + operandY;
                            break;
                        case "-":
                            result = operandX - operandY;
                            break;
                        case "*":
                            result = operandX * operandY;
                            break;
                        case "/":
                            result = operandX / operandY;
                            break;
                        default:
                            break;
                    }
                    operands.Push(result);
                }
                else
                {
                    operands.Push(Int32.Parse(item));
                }
            }
            return operands.Peek();
        }
    }

Python代码：  
注意：1. Python中没有switch…case语句；2. Python中的除法和C语言中的除法不一样，所以对负数我们要做特殊处理，得到的结果才能和C系语言的结果一样

class Solution:
        # @param tokens, a list of string
        # @return an integer
        def evalRPN(self, tokens):
            operands = []
            operators = ['+', '-', '*', '/']
            for i in range(len(tokens)):
                if tokens[i] in operators:
                    operandy = operands.pop()
                    operandx = operands.pop()
                    if tokens[i] == '+':
                        result = operandx + operandy
                    elif tokens[i] == '-':
                        result = operandx - operandy
                    elif tokens[i] == '*':
                        result = operandx * operandy
                    #because the division operation is differnt from the C
                    #so here we must hadle the negative number
                    elif tokens[i] == '/':
                        if (operandx > 0) ^ (operandy > 0):
                            result = -1 * (abs(operandx) / abs(operandy))
                        else:
                            result = operandx / operandy
                    operands.append(result)
                else:
                    operands.append(int(tokens[i]))
            return operands.pop()

[Link 1]: http://blog.csdn.net/theonegis/article/details/43707261