题解 | #牛牛与后缀表达式#

题目链接

题目描述

给定一个后缀表达式s，计算它的结果。例如，1+1对应的后缀表达式为1#1#+，#作为操作数的结束符号。表达式中只含有+、-、*三种运算，不包含除法。本题保证表达式一定合法，且计算过程和计算结果的绝对值一定不会超过 long long。

示例1 输入： "1#1#+" 输出： 2

示例2 输入： "12#3#+15#*" 输出： 225

解题思路

后缀表达式（也称逆波兰表达式）求值是栈的经典应用。我们从左到右扫描表达式，遇到数字就进栈，遇到运算符就出栈两个数字计算，然后将结果压入栈中。

具体步骤如下：

初始化一个空栈：这个栈用来存放待计算的操作数。
遍历表达式字符串：从左到右逐个字符处理。
处理操作数：如果当前字符是数字，我们需要继续向后读取，直到遇到#为止，这样可以解析出可能的多位数。然后将这个完整的数字字符串转换为整数，压入栈中。
处理运算符：如果当前字符是+、-或*，就从栈中弹出两个元素。注意弹出的顺序，第一个弹出的是右操作数，第二个弹出的是左操作数。
计算并入栈：用弹出的运算符对这两个数进行计算，然后把计算结果压回栈中。
返回结果：当整个表达式遍历完毕后，栈中只会留下一个元素，这个元素就是表达式的最终结果。

代码

cpp
java
python

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定一个后缀表达式，返回它的结果
     * @param str string字符串
     * @return long长整型
     */
    long long legalExp(string str) {
        stack<long long> s;
        for (int i = 0; i < str.length(); ) {
            if (isdigit(str[i])) {
                long long num = 0;
                while (i < str.length() && str[i] != '#') {
                    num = num * 10 + (str[i] - '0');
                    i++;
                }
                s.push(num);
            } else if (str[i] == '+' || str[i] == '-' || str[i] == '*') {
                long long b = s.top(); s.pop();
                long long a = s.top(); s.pop();
                if (str[i] == '+') s.push(a + b);
                else if (str[i] == '-') s.push(a - b);
                else s.push(a * b);
                i++;
            } else { // 跳过 '#'
                i++;
            }
        }
        return s.top();
    }
};

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定一个后缀表达式，返回它的结果
     * @param str string字符串
     * @return long长整型
     */
    public long legalExp(String str) {
        Stack<Long> stack = new Stack<>();
        for (int i = 0; i < str.length(); ) {
            char c = str.charAt(i);
            if (Character.isDigit(c)) {
                long num = 0;
                while (i < str.length() && str.charAt(i) != '#') {
                    num = num * 10 + (str.charAt(i) - '0');
                    i++;
                }
                stack.push(num);
            } else if (c == '+' || c == '-' || c == '*') {
                long b = stack.pop();
                long a = stack.pop();
                switch (c) {
                    case '+':
                        stack.push(a + b);
                        break;
                    case '-':
                        stack.push(a - b);
                        break;
                    case '*':
                        stack.push(a * b);
                        break;
                }
                i++;
            } else { // 跳过 '#'
                i++;
            }
        }
        return stack.pop();
    }
}

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 给定一个后缀表达式，返回它的结果
# @param str string字符串
# @return long长整型
#
class Solution:
    def legalExp(self, str: str) -> int:
        stack = []
        i = 0
        n = len(str)
        while i < n:
            if str[i] in "+-*":
                b = stack.pop()
                a = stack.pop()
                if str[i] == '+':
                    stack.append(a + b)
                elif str[i] == '-':
                    stack.append(a - b)
                elif str[i] == '*':
                    stack.append(a * b)
                i += 1
            elif str[i] == '#':
                i += 1
            else:  # 数字
                j = i
                while j < n and str[j] != '#':
                    j += 1
                stack.append(int(str[i:j]))
                i = j
        
        return stack[0]

算法及复杂度

算法：栈
时间复杂度： $\mathcal{O}(N)$ ，其中 $N$ 是输入字符串的长度。我们只需要对字符串进行一次完整的遍历。
空间复杂度： $\mathcal{O}(M)$ ，其中 $M$ 是表达式中操作数的数量。栈所需空间取决于表达式中同时存在于栈中的最大操作数数量。在最坏情况下（例如 "1#2#3#...#+*..."），空间复杂度可能接近 $\mathcal{O}(N)$ 。