逆波兰表达式是编译原理中的一种基本表达式,利用Python语言也可以实现逆波兰表达式的输出,这里举例实践说明:
什么是逆波兰表达式?
逆波兰表达式又叫做后缀表达式。在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之间,所以,这种表示法也称为中缀表示。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法。按此方法,每一运算符都置于其运算对象之后,故称为后缀表示。
举例实现:
# -*- coding: utf-8 -*- symbol_priority = {} symbol_priority[0] = ['#'] symbol_priority[1] = ['('] symbol_priority[2] = ['+', '-'] symbol_priority[3] = ['*', '/'] symbol_priority[4] = [')'] def comparePriority(symbol, RPN_stack, symbol_stack): '''Compare priority between two symbols''' global symbol_priority if len(symbol_stack) > 0: symbol_pop = symbol_stack.pop() else: return for list in symbol_priority.values(): if (symbol in list) and (symbol_pop in list): '''same priority''' symbol_stack.append(symbol_pop) symbol_stack.append(symbol) return elif symbol in list: '''symbol is smaller''' RPN_stack.append(symbol_pop) #recusion call comparePriority(symbol, RPN_stack, symbol_stack) return elif symbol_pop in list: '''symbol is bigger''' symbol_stack.append(symbol_pop) symbol_stack.append(symbol) return else: continue symbol_stack.append(symbol_pop) return def scanEveryone(input_string, RPN_stack, symbol_stack): for ch in input_string: if ch.isdigit(): RPN_stack.append(ch) else: if len(symbol_stack) > 0: if ch == '(': symbol_stack.append(ch) elif ch == ')': while True: symbol_pop = symbol_stack.pop() if symbol_pop == '(': break else: RPN_stack.append(symbol_pop) else: comparePriority(ch, RPN_stack, symbol_stack) else: symbol_stack.append(ch) def scanInput(RPN_stack, symbol_stack): input_string = raw_input() input_string += '#' scanEveryone(input_string, RPN_stack, symbol_stack) def calRPN(RPN_stack): value_stack = [] RPN_stack.append('#') for value in RPN_stack: if value == '#': return value_stack.pop() break if value.isdigit(): value_stack.append(value) else: right_value = value_stack.pop() left_value = value_stack.pop() cal_string = left_value + value + right_value value_stack.append(str(eval(cal_string))) def main(): RPN_stack = [] symbol_stack = [] scanInput(RPN_stack, symbol_stack) print calRPN(RPN_stack) if __name__ == '__main__': main()
calRPN.py
# -*- coding: utf-8 -*- symbol_priority = {} symbol_priority[0] = ['#'] symbol_priority[1] = ['('] symbol_priority[2] = ['+', '-'] symbol_priority[3] = ['*', '/'] symbol_priority[4] = [')'] def comparePriority(symbol, RPN_stack, symbol_stack): '''Compare priority between two symbols''' global symbol_priority if len(symbol_stack) > 0: symbol_pop = symbol_stack.pop() else: return for list in symbol_priority.values(): if (symbol in list) and (symbol_pop in list): '''same priority''' symbol_stack.append(symbol_pop) symbol_stack.append(symbol) return elif symbol in list: '''symbol is smaller''' RPN_stack.append(symbol_pop) #recusion call comparePriority(symbol, RPN_stack, symbol_stack) return elif symbol_pop in list: '''symbol is bigger''' symbol_stack.append(symbol_pop) symbol_stack.append(symbol) return else: continue symbol_stack.append(symbol_pop) return def scanEveryone(input_string, RPN_stack, symbol_stack): for ch in input_string: if ch.isdigit(): RPN_stack.append(ch) else: if len(symbol_stack) > 0: if ch == '(': symbol_stack.append(ch) elif ch == ')': while True: symbol_pop = symbol_stack.pop() if symbol_pop == '(': break else: RPN_stack.append(symbol_pop) else: comparePriority(ch, RPN_stack, symbol_stack) else: symbol_stack.append(ch) def scanInput(RPN_stack, symbol_stack): input_string = raw_input() input_string += '#' scanEveryone(input_string, RPN_stack, symbol_stack) def calRPN(RPN_stack): value_stack = [] RPN_stack.append('#') for value in RPN_stack: if value == '#': return value_stack.pop() break if value.isdigit(): value_stack.append(value) else: right_value = value_stack.pop() left_value = value_stack.pop() cal_string = left_value + value + right_value value_stack.append(str(eval(cal_string))) def main(): RPN_stack = [] symbol_stack = [] scanInput(RPN_stack, symbol_stack) print calRPN(RPN_stack) if __name__ == '__main__': main()
常见问题FAQ
- 免费下载或者VIP会员专享资源能否直接商用?
- 本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
- 提示下载完但解压或打开不了?
- 找不到素材资源介绍文章里的示例图片?
- 模板不会安装或需要功能定制以及二次开发?
发表评论
还没有评论,快来抢沙发吧!