四则运算 计算器——自己写一遍
标签： 四则运算 计算器——自己写一遍 HarmonyOS博客 51CTO博客
2023-05-31 18:24:21 74浏览
四则运算表达式
四则运算表达式
一种不需要括号的后缀表达法，我们把它称为逆波兰（Reverse Polish Notation ， RPN）表示。它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式，解决了四则运算中括号改变运算符优先级的问题。
我们先来看看，对于"9+(3-1)×3+10÷2"，如果要用后缀表示法应该是什么样子：“9 3 1 - 3 * + 10 2 / +” ，这样的表达式称为后缀表达式，叫后缀的原因在于所有的符号都是在要运算数字的后面出现。
中缀表达式转后缀表达式
转换思路如下：
使用一个辅助栈来存储操作符;
遇到数字, 直接输出;
遇到左括号'(', 进栈;
遇到操作符(操作符'+','-','*','/')时, 若操作符优先级大于栈顶操作符, 则直接进栈, 注意：此时'('的优先级最低, 即栈顶符号为'(', 则操作符直接进栈; 若操作符优先级等于或小于栈顶优先级时, 则栈顶操作符出栈并输出, 直到满足操作符优先级大于栈顶操作符优先级;
遇到右括号')', 则将辅助栈中操作符出栈并输出, 直到遇到'(', 并且'('也要出栈
ref：https://leetcode.cn/problems/basic-calculator-iii/solution/ni-bo-lan-biao-da-shi-jie-fa-chong-chong-0pr6/我们把平时所用的标准四则运算表达式，即“9+(3-1)×3+10÷2”叫做中缀表达式。因为所有的运算符号都在两数字的中间。
中缀表达式 “9+(3-1)×3+10÷2” 转化为后缀表达式 “9 3 1 - 3 * + 10 2 / +” 。
规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。（见上面黄色部分）
1.初始化一空栈，用来对符号进出栈使用。如图6左图所示。
2.第一个字符是数字9，输出9，后面是符号“+”，进栈。如图6的右图所示。
图6
3.第三个字符时“（” ， 依然是符号，因其只是左括号，还没配对，故进栈。如图7左图所示。
4.第四个字符是数字3，输出，总表达式为9 3，接着是“—”，进栈。如图7右图所示。
图7
5.接下来是数字1，输出，总表达式为9 3 1，后面是符号“)” ， 此时，我们需要去匹配此前的“(” ， 所以栈顶依次出栈，并输出，直到“(”出栈为止。此时左括号上方只有“—” ， 因此输出“—”。总的输出表达式为9 3 1 —
6.紧接着是符号“×” ，因为此时的栈顶符号为“+”号，优先级低于“×” ，因此不输出，“*”进栈（没有直接输出？为啥？因为后面可能还有比*更高优先级的运算符号）。接着是数字3，输出，总的表达式为 9 3 1 — 3 。 如图8右图所示。
图8
7.之后是符号“+” ，此时当前栈顶元素“*”比这个“+”的优先级高，因此栈中元素出栈并输出（没有比“+”号更低的优先级，所以全部出栈），总输出表达式为9 3 1 — 3 * + 。然后将当前这个符号“+”进栈。也就是说，前6张图的栈底的“+”是指中缀表达式中开头的9后面那个“+” ，而图9左图中的栈底（也是栈顶）的“+”是指“9+(3-1)×3+”中的最后一个“+”。
8.紧接着数字10，输出，总表达式变为9 3 1 — 3 * + 10 。 后是符号“÷” ，所以“/”进栈。如图9右图所示。
图9
9.最后一个数字2，输出，总的表达式为9 3 1 — 3 * + 10 2 。如图10左图所示。
10.因已经到最后，所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为 9 3 1 — 3 * + 10 2 / + 。如图10右图所示。
图10
逆波兰计算器的计算过程为：从左到右扫描后缀表达式，遇到数字就入栈，遇到操作符就从栈弹出两个数字，然后计算得到的值继续入栈，继续扫描表达式，直到扫描完毕得到结果。
从逆波兰计算器的扫描过程可以看到，过程特别简单，代码写起来也比较容易。
好了，到了后缀表达式求值了！！！如下：很简单
150. 逆波兰表达式求值
难度中等665
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
- 有效的算符为
'+'、'-'、'*'和'/'。 - 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
示例 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 <= 104-
tokens[i]是一个算符（"+"、"-"、"*"或"/"），或是在范围[-200, 200]内的一个整数
import operator
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
n = len(tokens)
op = {"+": operator.add, "-": operator.sub, "/": lambda a, b: int(a/b), "*": operator.mul}
for i in range(n):
if tokens[i] not in op:
stack.append(int(tokens[i]))
else:
val1 = stack.pop()
val2 = stack.pop()
val = op[tokens[i]](val2, val1)
stack.append(val)
return stack.pop()
到了整个实现了！！！
772. 基本计算器 III
难度困难141
实现一个基本的计算器来计算简单的表达式字符串。
表达式字符串只包含非负整数，算符 +、-、*、/ ，左括号 ( 和右括号 ) 。整数除法需要 向下截断 。
你可以假定给定的表达式总是有效的。所有的中间结果的范围均满足 [-231, 231 - 1] 。
注意：你不能使用任何将字符串作为表达式求值的内置函数，比如 eval（) 。
示例 1：
输入：s = "1+1"
输出：2示例 2：
输入：s = "6-4/2"
输出：4示例 3：
输入：s = "2*(5+5*2)/3+(6/2+8)"
输出：21
提示：
1 <= s <= 104-
s由整数、'+'、'-'、'*'、'/'、'('和')'组成 -
s是一个 有效的 表达式
我写的代码实现如下：
class Solution:
def calculate(self, s: str) -> int:
exp = self.reverse_polish_exp(s)
return self.eval_polish_exp(exp)
def get_priority(self, c):
priority = {"+": 1, "-": 1, "*": 2, "/": 2}
return priority[c]
def reverse_polish_exp(self, s):
"""
中缀表达式转换为逆波兰表达式
"""
n = len(s)
stack = []
result = []
i = 0
while i < n:
# 遇到空格, 直接跳过
if s[i] == ' ':
pass
# 遇到数字
elif s[i].isdigit():
start = i
while i + 1 < n and s[i+1].isdigit():
i += 1
num = int(s[start:i+1])
result.append(num)
# 遇到左括号, 直接进栈
elif s[i] == '(':
stack.append('(')
# 遇到')'不断出栈, 直到遇到'('括号或栈为空
elif s[i] == ')':
while stack[-1] != '(':
result.append(stack.pop())
stack.pop()
# 遇到 '+', '-', '*', '/'操作符, 需要根据运算优先级进行相应处理
else:
# 1. 若栈为空, 栈顶元素为'(', 并且当前操作符大于栈顶运算符, 则直接进栈
# 3. 当前操作符小于或等于栈顶运算符, 则不断进行出栈, 直到满足条件1
while stack and stack[-1] != '(' and self.get_priority(s[i]) <= self.get_priority(stack[-1]):
result.append(stack.pop())
stack.append(s[i])
i += 1
while stack:
result.append(stack.pop())
return result
def eval_polish_exp(self, tokens):
stack = []
n = len(tokens)
op = {"+": operator.add, "-": operator.sub, "/": lambda a, b: int(a/b), "*": operator.mul}
for i in range(n):
if tokens[i] not in op:
stack.append(int(tokens[i]))
else:
val1 = stack.pop()
val2 = stack.pop()
val = op[tokens[i]](val2, val1)
stack.append(val)
return stack.pop()
227. 基本计算器 II
难度中等657
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval（) 。
示例 1：
输入：s = "3+2*2"
输出：7示例 2：
输入：s = " 3/2 "
输出：1示例 3：
输入：s = " 3+5 / 2 "
输出：5
是上面那个题目的简化，没有括号的判定，代码如下：class Solution:
def calculate(self, s: str) -> int:
exp = self.reverse_polish_exp(s)
return self.eval_polish_exp(exp)
def get_priority(self, c):
priority = {"+": 1, "-": 1, "*": 2, "/": 2}
return priority[c]
def reverse_polish_exp(self, s):
"""
中缀表达式转换为逆波兰表达式
"""
n = len(s)
stack = []
result = []
i = 0
while i < n:
# 遇到空格, 直接跳过
if s[i] == ' ':
pass
# 遇到数字
elif s[i].isdigit():
start = i
while i + 1 < n and s[i+1].isdigit():
i += 1
num = int(s[start:i+1])
result.append(num)
# 遇到 '+', '-', '*', '/'操作符, 需要根据运算优先级进行相应处理
else:
# 1. 若栈为空, 栈顶元素为'(', 并且当前操作符大于栈顶运算符, 则直接进栈
# 3. 当前操作符小于或等于栈顶运算符, 则不断进行出栈, 直到满足条件1
while stack and self.get_priority(s[i]) <= self.get_priority(stack[-1]):
result.append(stack.pop())
stack.append(s[i])
i += 1
while stack:
result.append(stack.pop())
return result
def eval_polish_exp(self, tokens):
stack = []
n = len(tokens)
op = {"+": operator.add, "-": operator.sub, "/": lambda a, b: int(a/b), "*": operator.mul}
for i in range(n):
if tokens[i] not in op:
stack.append(int(tokens[i]))
else:
val1 = stack.pop()
val2 = stack.pop()
val = op[tokens[i]](val2, val1)
stack.append(val)
return stack.pop()
也可以使用双栈，如下：
class Solution:
def calculate(self, s: str) -> int:
op = {"+": operator.add, "-": operator.sub, "/": lambda a, b: int(a/b), "*": operator.mul}
n = len(s)
op_stack = []
data_stack = []
i = 0
while i < n:
# 遇到空格, 直接跳过
if s[i] == ' ':
pass
# 遇到数字
elif s[i].isdigit():
start = i
while i + 1 < n and s[i+1].isdigit():
i += 1
num = int(s[start:i+1])
data_stack.append(num)
# 遇到 '+', '-', '*', '/'操作符, 需要根据运算优先级进行相应处理
else:
# 和s[i]操作符比较，栈里有优先级更高的操作符，那说明之前的运算操作要计算了
# 例如：3+2-5*0+999 ==> 3+2- 遇到-的时候，就可以计算3+2了，因为二者同等优先级
# 再往前走，看到*，暂时还不能计算，因为没有看到后面的数字，先入栈，再往后走看到0
# 继而看到+，此时stack里*优先级更高，可以计算5*0了！计算完成以后，之前的-也可以计算了
# 所以必须是while循环，而不能是if！
while op_stack and self.get_priority(s[i]) <= self.get_priority(op_stack[-1]):
char = op_stack.pop()
num1 = data_stack.pop()
num2 = data_stack.pop()
data_stack.append(op[char](num2, num1))
print(data_stack)
print(op_stack)
op_stack.append(s[i])
i += 1
while op_stack:
char = op_stack.pop()
num1 = data_stack.pop()
num2 = data_stack.pop()
data_stack.append(op[char](num2, num1))
return data_stack[-1]
def get_priority(self, c):
priority = {"+": 1, "-": 1, "*": 2, "/": 2}
return priority[c]
好博客就要一起分享哦！分享海报
此处可发布评论
评论（0）展开评论
展开评论
