后缀表达式

剑指 Offer II 036. 后缀表达式

根据逆波兰表示法，求该后缀表达式的计算结果。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：
该算式转化为常见的中缀算术表达式为：
  ((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

提示：

1 <= tokens.length <= 10⁴
tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 [-200, 200] 内的整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

注意：本题与主站 150 题相同： https://leetcode.cn/problems/evaluate-reverse-polish-notation/

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int evalRPN(vector<string>& tokens) { } };

golang 解法, 执行用时: 4 ms, 内存消耗: 4.6 MB, 提交时间: 2022-11-22 11:21:01

func evalRPN(tokens []string) int {
    stack := []int{}
    for _, token := range tokens {
        val, err := strconv.Atoi(token)
        if err == nil {
            stack = append(stack, val)
        } else {
            num1, num2 := stack[len(stack)-2], stack[len(stack)-1]
            stack = stack[:len(stack)-2]
            switch token {
            case "+":
                stack = append(stack, num1+num2)
            case "-":
                stack = append(stack, num1-num2)
            case "*":
                stack = append(stack, num1*num2)
            default:
                stack = append(stack, num1/num2)
            }
        }
    }
    return stack[0]
}

golang 解法, 执行用时: 4 ms, 内存消耗: 4.4 MB, 提交时间: 2022-11-22 11:20:49

func evalRPN(tokens []string) int {
    stack := make([]int, (len(tokens)+1)/2)
    index := -1
    for _, token := range tokens {
        val, err := strconv.Atoi(token)
        if err == nil {
            index++
            stack[index] = val
        } else {
            index--
            switch token {
            case "+":
                stack[index] += stack[index+1]
            case "-":
                stack[index] -= stack[index+1]
            case "*":
                stack[index] *= stack[index+1]
            default:
                stack[index] /= stack[index+1]
            }
        }
    }
    return stack[0]
}

python3 解法, 执行用时: 52 ms, 内存消耗: 16.7 MB, 提交时间: 2022-11-22 11:20:34

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        op_to_binary_fn = {
            "+": add,
            "-": sub,
            "*": mul,
            "/": lambda x, y: int(x / y),   # 需要注意 python 中负数除法的表现与题目不一致
        }

        n = len(tokens)
        stack = [0] * ((n + 1) // 2)
        index = -1
        for token in tokens:
            try:
                num = int(token)
                index += 1
                stack[index] = num
            except ValueError:
                index -= 1
                stack[index] = op_to_binary_fn[token](stack[index], stack[index + 1])
            
        return stack[0]

python3 解法, 执行用时: 48 ms, 内存消耗: 16.4 MB, 提交时间: 2022-11-22 11:20:08

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        op_to_binary_fn = {
            "+": add,
            "-": sub,
            "*": mul,
            "/": lambda x, y: int(x / y),   # 需要注意 python 中负数除法的表现与题目不一致
        }

        stack = list()
        for token in tokens:
            try:
                num = int(token)
            except ValueError:
                num2 = stack.pop()
                num1 = stack.pop()
                num = op_to_binary_fn[token](num1, num2)
            finally:
                stack.append(num)
            
        return stack[0]

python3 解法, 执行用时: 96 ms, 内存消耗: 16.7 MB, 提交时间: 2022-11-22 11:19:20

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        oper = '+-*/'
        data = list()
        for token in tokens:
            if token in oper:
                right = data.pop()
                left = data.pop()
                data.append(int(eval(f'{left}{token}{right}')))
            else:
                data.append(token)
        return int(data[0])

php 解法, 执行用时: 48 ms, 内存消耗: 20.7 MB, 提交时间: 2022-11-22 11:03:28

class Solution {

    /**
     * @param String[] $tokens
     * @return Integer
     */
    function evalRPN($tokens) {
        $data = [];
        $sig = ['+', '-', '*', '/'];
        foreach ( $tokens as $token ) {
            if ( in_array($token, $sig) ) {
                $right = array_pop($data);
                $left = array_pop($data);
                $data[] = eval("return intval({$left}{$token}({$right}));");
            } else {
                $data[] = $token;
            }
        }
        return intval($data[0]);
    }
}

上一题

下一题

详情