Leetcode: Evaluate Reverse Polish Notation-蒲公英云

Leetcode: Evaluate Reverse Polish Notation

迷南。 2022-08-05 14:28 115阅读 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

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

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()