科技类网站怎么做,做外贸需要关注的网站有什么好处,关键词优化资讯,注册城乡规划师是干什么的文章目录 一、题目描述示例 1示例 2示例 3 二、代码三、解题思路 一、题目描述
给你一个字符串表达式 s #xff0c;请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-2^31, 2^31 - 1]的范围内… 文章目录 一、题目描述示例 1示例 2示例 3 二、代码三、解题思路 一、题目描述
给你一个字符串表达式 s 请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-2^31, 2^31 - 1]的范围内。
注意不允许使用任何将字符串作为数学表达式计算的内置函数比如 eval() 。
示例 1
输入s 32*2
输出7示例 2
输入s 3/2
输出1示例 3
输入s 35 / 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位数及其以上的情况如果之间转化为后缀表达式则会导致数字连接到一块所以需要对数字和运算符进行分隔将表达式转化为如下格式“124/5” “12 4 / 5” ② 转化为后缀表达式当遇到2位数及以上的数字时需要将其看做是一个数用空格分隔不同数。例如 中缀表达式: 12 4 / 5 后缀表达式: 12 4 5 / 不同的数之间用空格分开 ③ 计算后缀表达式找第一个运算符向左找最近的2个数进行计算重复这一过程最后得到一个值返回即可。
