227. 基本计算器 II Python

---

一、题目描述

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-2^31, 2^31 - 1]的范围内。

注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1

输入：s = "3+2*2"
输出：7

示例 2

输入：s = " 3/2 "
输出：1

示例 3

输入：s = " 3+5 / 2 "
输出：5

提示：
1 <= s.length <= 3 * 10^5
s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
s 表示一个 有效表达式
表达式中的所有整数都是非负整数，且在范围 [0, 2^31 - 1] 内
题目数据保证答案是一个 32-bit 整数

二、代码

代码如下：

class Solution:def calculate(self, s: str) -> int:def is_operator(char):return char in "+-*/^"def infix_to_postfix(expression):def precedence(operator):precedence_dict = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}return precedence_dict.get(operator, 0)def infix_to_postfix_internal(expression_tokens):output = []operator_stack = []for token in expression_tokens:if token.isnumeric():  # 如果是数字，直接添加到输出output.append(token)elif token == '(':  # 如果是左括号，压入栈operator_stack.append(token)elif token == ')':  # 如果是右括号，将栈顶的操作符弹出并添加到输出，直到遇到左括号while operator_stack and operator_stack[-1] != '(':output.append(operator_stack.pop())if operator_stack and operator_stack[-1] == '(':operator_stack.pop()elif is_operator(token):  # 如果是操作符，处理操作符的优先级while (operator_stack andoperator_stack[-1] != '(' andprecedence(token) <= precedence(operator_stack[-1])):output.append(operator_stack.pop())operator_stack.append(token)while operator_stack:  # 将栈中剩余的操作符全部添加到输出output.append(operator_stack.pop())return ' '.join(output)# 将输入的表达式字符串按空格分割成标记列表expression_tokens = expression.split()# 调用内部函数进行转换postfix_expression = infix_to_postfix_internal(expression_tokens)return postfix_expressiondef add_spaces_to_infix(expression):operators = "+-*/^"result = []for char in expression:if char in operators or char in "()":result.append(f" {char} ")else:result.append(char)return ''.join(result)infix_expression = s.replace(" ", "")print(infix_expression)spaced_infix_expression = add_spaces_to_infix(infix_expression)print(spaced_infix_expression)postfix_expression = infix_to_postfix(spaced_infix_expression)print("中缀表达式:", spaced_infix_expression)print("后缀表达式:", postfix_expression)stack = []for token in postfix_expression.split():if token.isnumeric():stack.append(int(token))elif is_operator(token):operand2 = stack.pop()operand1 = stack.pop()if token == '+':result = operand1 + operand2elif token == '-':result = operand1 - operand2elif token == '*':result = operand1 * operand2elif token == '/':if operand2 == 0:raise ValueError("Division by zero")result = int(operand1 / operand2)stack.append(result)print(int(stack[0]))return int(stack[0])

---

三、解题思路

本题本质是要求通过字符串来计算表达式，且不能直接使用eval方法对字符串直接进行转化计算。本题解题思路为：将字符串（前缀表达式）转化为后缀表达式，然后通过计算后缀表达式得到结果。
① 因为涉及到字符可能会出现2位数及其以上的情况，如果之间转化为后缀表达式，则会导致数字连接到一块，所以需要对数字和运算符进行分隔，将表达式转化为如下格式：“12+4/5” => “12 + 4 / 5”
② 转化为后缀表达式，当遇到2位数及以上的数字时，需要将其看做是一个数，用空格分隔不同数。例如：
中缀表达式: 12 + 4 / 5
后缀表达式: 12 4 5 / +
不同的数之间用空格分开
③ 计算后缀表达式，找第一个运算符，向左找最近的2个数进行计算，重复这一过程，最后得到一个值返回即可。