本文共 2344 字，大约阅读时间需要 7 分钟。

题目：（中等）

标签：字符串、栈

LeetCode的Python执行用时随缘，只要时间复杂度没有明显差异，执行用时一般都在同一个量级，仅作参考意义。

解法一（标准逆波兰表达式求值）：

class Solution:    def calculate(self, s: str) -> int:        mark_level = {
   "+": 0, "-": 0, "*": 1, "/": 1}  # 定义符号优先级        # 合并多位数字        group = []  # 合并数字组        for ch in s:            if ch.isdigit():                if group and group[-1].isdigit():                    group[-1] += ch                else:                    group.append(ch)            else:                group.append(ch)        # 将中缀表达式转换为后缀表达式        expression = []  # 表达式        stack = []  # 符号栈        for ch in group:            if ch.isdigit():                expression.append(ch)            elif ch in mark_level:                while stack and mark_level[stack[-1]] >= mark_level[ch]:                    expression.append(stack.pop())                stack.append(ch)        while stack:            expression.append(stack.pop())        # 后缀表达式求值        stack = []  # 数字栈        for ch in expression:            if ch.isdigit():                stack.append(int(ch))            else:                b = stack.pop()                a = stack.pop()                if ch == "+":                    stack.append(a + b)                elif ch == "-":                    stack.append(a - b)                elif ch == "*":                    stack.append(a * b)                elif ch == "/":                    stack.append(a // b)        return stack[0]

解法二（直接用栈求解）：

class Solution:    def calculate(self, s: str) -> int:        marks = {
   "+", "-", "*", "/"}        stack = []  # 多项式栈        now_num = ""  # 当前数字        last_mark = "+"  # 上一个符号        for ch in s + "+":  # 在结尾添加无意义的运算符，使最后一个数字可以被计算            if ch.isdigit():                now_num += ch            elif ch in marks:                num = int(now_num)                if last_mark == "+":                    stack.append(num)                elif last_mark == "-":                    stack.append(-num)                elif last_mark == "*":                    stack[-1] *= num                else:                    stack[-1] = int(stack[-1] / num)                now_num = ""                last_mark = ch        return sum(stack)

转载地址：https://dataartist.blog.csdn.net/article/details/107997796 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！