如何理解前缀,后缀,中缀表达式转化求值问题
这篇文章主要讲解了“如何理解前缀,后缀,中缀表达式转化求值问题”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“如何理解前缀,后缀,中缀表达式转化求值问题”吧!
创新互联-专业网站定制、快速模板网站建设、高性价比香格里拉网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式香格里拉网站制作公司更省心,省钱,快速模板网站建设找我们,业务覆盖香格里拉地区。费用合理售后完善,十多年实体公司更值得信赖。
算法,一门既不容易入门,也不容易精通的学问。
上次介绍如何利用栈实现中缀表达式求值,如果我是出题官,当然要考前缀,后缀,中缀表达式相互转换,然后就变成了利用栈实现前缀和后缀表达式求值。
前缀,后缀,中缀表达式相互转换及其运算,可以说是计算机考研的一个重点。
首先看下面所示表格:
注意:前序表达式和后序表达式是没有扩号
中缀表达式转前缀表达式求值
中缀表达式转前缀表达式的规则:
1、反转输入字符串,如“2*3/(2-1)+3*(4-1)” 反转后为“ )1-4(*3+)1-2(/3*2”, 2、从字符串中取出下一个字符 2.1.如果是操作数,直接输出 2.2.如果是“)”,压入栈中 2.3.如果是运算符但不是“(”,“)”,则不断循环进行以下处理 2.3.1.如果栈为空,则此运算符进栈,结束此步骤 2.3.2.如果栈顶是“)”,则此运算符进栈,结束此步骤 2.3.2.如果此运算符与栈顶优先级相同或者更高,此运算符进栈,结束此步骤 2.3.4.否则,运算符连续出栈,直到满足上述三个条件之一,然后此运算符进栈 2.4、如果是“(”,则运算符连续出栈,直到遇见“)”为止,将“)”出栈且丢弃之 3、如果还有更多的字符串,则转到第2步 4、不在有未处理的字符串了,输出栈中剩余元素 5、再次反转字符串得到最终结果
经过上面的步骤,得到的输出既是转换得到的前缀表达式。
前缀表达式的计算方法:对前缀表达式从后向前扫描,设定一个操作数栈,如果是操作数,则将其直接入栈,如果是操作符,则从栈中弹出操作符对应的操作数进行运算,并将计算结果压栈。直至从右到左扫描完毕整个前缀表达式,这时操作数栈中应该只有一个元素,该元素的值则为前缀表达式的计算结果。
上面的过程使用数据结构栈来实现,具体代码如下
''' @Author:Runsen @WeChat:RunsenLiu @微信公众号:Python之王 @CSDN:https://blog.csdn.net/weixin_44510615 @Github:https://github.com/MaoliRUNsen @Date:2020/12/17 ''' import re class Stack(): def __init__(self): self.items = [] def push(self, item): return self.items.append(item) def pop(self): return self.items.pop() def size(self): return len(self.items) def peek(self): return self.items[len(self.items) - 1] def display(self): print(self.items) def infix_to_prefix(s): prec = { '*': 3, '/': 3, '+': 2, '-': 2, '(': 4, ')': 1 } a = re.findall('[1-9]\d*|[\+\-\*\/\(\)]', input('请输入中缀表达式:')) prefix = [] for x in a[::-1]: if re.match('[0-9]', x): #操作数,直接输出 prefix.append(x) else: #如果是“)”,压入栈中 if x == ')': s.push(x) elif x == '(': while True: i = s.pop() if i == ')': break else: prefix.append(i) else: if s.size() > 0 and prec[x] <= prec[s.peek()]: prefix.append(s.pop()) s.push(x) for _ in range(s.size()): prefix.append(s.pop()) return prefix[::-1] def cal_prefix(s, prefix): # 思路:对前缀表达式从后向前扫描,设定一个操作数栈,如果是操作数,则将其直接入栈,如果是操作符,则从栈中弹出操作符对应的操作数进行运算,并将计算结果压栈。 # 直至从右到左扫描完毕整个前缀表达式,这时操作数栈中应该只有一个元素,该元素的值则为前缀表达式的计算结果。 for x in prefix[::-1]: if re.match('[0-9]', x): s.push(x) else: a2 = int(s.pop()) a1 = int(s.pop()) if x == '*': a = a1 * a2 elif x == '/': a = a2 / a1 elif x == '+': a = a1 + a2 else: a = a2 - a1 s.push(a) return s.pop() if __name__ == '__main__': s = Stack() prefix = infix_to_prefix(s) print('前缀表达式:', prefix) prefix_val = cal_prefix(s, prefix) print('前缀表达式计算结果:', prefix_val) 请输入中缀表达式:2*3/(2-1)+3*(4-1) 前缀表达式: ['+', '*', '2', '/', '3', '-', '2', '1', '*', '3', '-', '4', '1'] 前缀表达式计算结果: 15 请输入中缀表达式:9+(3-1*2)*3+10/2 前缀表达式: ['+', '+', '9', '*', '-', '3', '*', '1', '2', '3', '/', '10', '2'] 前缀表达式计算结果: 17
中缀表达式转换为后缀表达式求值
中缀表达式转后缀表达式的规则:
1.遇到操作数,直接输出;
2.栈为空时,遇到运算符,入栈;
3.遇到左括号,将其入栈;
4.遇到右括号,执行出栈操作,并将出栈的元素输出,直到弹出栈的是左括号,左括号不输出;
5.遇到其他运算符’+”-”*”/’时,弹出所有优先级大于或等于该运算符的栈顶元素,然后将该运算符入栈;
6.最终将栈中的元素依次出栈,输出。
经过上面的步骤,得到的输出既是转换得到的后缀表达式。
后缀表达式的计算方法:对后缀表达式从前向后扫描,设定一个操作数栈,如果是操作数,则将其直接入栈,如果是操作符,则从栈中弹出操作符对应的操作数进行运算,并将计算结果压栈。直至从右到左扫描完毕整个后缀表达式,这时操作数栈中应该只有一个元素,该元素的值则为后缀表达式的计算结果。
上面的过程使用数据结构栈来实现,具体代码如下:
''' @Author:Runsen @WeChat:RunsenLiu @微信公众号:Python之王 @CSDN:https://blog.csdn.net/weixin_44510615 @Github:https://github.com/MaoliRUNsen @Date:2020/12/17 ''' import re class Stack(): def __init__(self): self.items = [] def push(self, item): return self.items.append(item) def pop(self): return self.items.pop() def size(self): return len(self.items) def peek(self): return self.items[len(self.items) - 1] def display(self): print(self.items) def infix_to_postfix (s): prec = { '*': 3, '/': 3, '+': 2, '-': 2, '(': 1, ')': 4 } a = re.findall('[1-9]\d*|[\+\-\*\/\(\)]', input('请输入中缀表达式:')) postfix = [] for x in a: if re.match('[0-9]', x): # 操作数,直接输出 postfix.append(x) else: # 如果是“(”,压入栈中 if x == '(': s.push(x) elif x == ')': while True: i = s.pop() if i == '(': break else: postfix.append(i) else: if s.size() > 0 and prec[x] <= prec[s.peek()]: postfix.append(s.pop()) s.push(x) for _ in range(s.size()): postfix.append(s.pop()) return postfix def cal_postfix (s, postfix): for x in postfix: if re.match('[0-9]', x): s.push(x) else: a1 = int(s.pop()) a2 = int(s.pop()) if x == '*': a = a1 * a2 elif x == '/': a = a2 / a1 elif x == '+': a = a1 + a2 else: a = a2 - a1 s.push(a) return s.pop() if __name__ == '__main__': s = Stack() postfix = infix_to_postfix(s) print('后缀表达式:', postfix) postfix_val = cal_postfix (s, postfix) print('后缀表达式计算结果:', postfix_val) 请输入中缀表达式:2*3/(2-1)+3*(4-1) ['2', '3', '*', '2', '1', '-', '/', '3', '4', '1', '-'] 后缀表达式: ['2', '3', '*', '2', '1', '-', '/', '3', '4', '1', '-', '*', '+'] 后缀表达式计算结果: 15 请输入中缀表达式:9+(3-1*2)*3+10/2 后缀表达式: ['9', '3', '1', '2', '*', '-', '3', '*', '10', '2', '/', '+', '+'] 后缀表达式计算结果: 17
其实此题是Leetcode第150题,逆波兰表达式求值。
根据 逆波兰表示法,求表达式的值。
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。
示例 1: 输入: ["2", "1", "+", "3", "*"] 输出: 9 解释: 该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9 示例 2: 输入: ["4", "13", "5", "/", "+"] 输出: 6 解释: 该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6
前缀表达式转中缀表达式
从右往左开始,取出一个操作符和操作符右边的两个数进行计算,并将计算的结果放过去,直到计算结束。以前缀表达式+/*23-21*3-41为例,将其转换为中缀表达式:
(1)取出-、4、1,计算并将结果放回得到+/*23-21*3(4-1);
(2)取出*、3、(4-1),计算并将结果放回得到+/*23-21(3*(4-1));
(3)取出-、2、1,计算并将结果放回得到+/*23(2-1)(3*(4-1));
(3)取出*、2、3,计算并将结果放回得到+/(2*3)(2-1)(3*(4-1));
(4)取出/、(2*3)、(2-1),计算并将结果放回得到+((2*3)/(2-1))(3*(4-1));
(5)取出+、((2*3)/(2-1))、(3*(4-1)),计算将结果放回得到((2*3)/(2-1))+(3*(4-1)),计算结束,显然计算结果为15。
后缀表达式转中缀表达式从左向右开始,取出一个操作符和操作符左边的两个数进行计算,并将计算的结果放过去,直到计算结束,以后缀表达式23*21-/341-*+为例,将其转换为中缀表达式:(1)取出2、3、*,计算并将结果放回得到(2*3)21-/341-*+;
(2)取出2,1,-,计算并将结果放回得到(2*3)(2-1)/341-*+;
(3)取出(2*3)、(2-1)、/,计算并将结果放回得到((2*3)/(2-1))341-*+;
(4)取出4,1,-,计算并将结果放回得到((2*3)/(2-1)) 3(4-1)*+;
(5)取出3,(4-1),*,计算并将结果放回得到((2*3)/(2-1)) 3*(4-1)+;
(6)取出((2*3)/(2-1)),3*(4-1),+,计算并将结果放回得到((2*3)/(2-1)) + 3*(4-1),显然计算结果为15。
感谢各位的阅读,以上就是“如何理解前缀,后缀,中缀表达式转化求值问题”的内容了,经过本文的学习后,相信大家对如何理解前缀,后缀,中缀表达式转化求值问题这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是创新互联,小编将为大家推送更多相关知识点的文章,欢迎关注!
当前名称:如何理解前缀,后缀,中缀表达式转化求值问题
本文路径:http://pwwzsj.com/article/ihiodc.html