第1关 基于栈的中缀算术表达式求值
时间: 2023-11-10 14:45:33 浏览: 118
题目描述
给定一个中缀算术表达式,计算它的值。
例如,给定表达式 3+4*5-2,其值为 3+4*5-2=21。
输入格式
共一行,为中缀算术表达式,其中不包含空格。
输出格式
共一行,为表达式的值。
数据范围
输入样例
3+4*5-2
输出样例
21
算法1
(栈) $O(n)$
栈中存储数字和运算符,遇到数字直接入栈,遇到运算符时,判断当前运算符和栈顶运算符的优先级,如果当前运算符优先级高于栈顶运算符,则直接入栈,如果当前运算符优先级低于等于栈顶运算符,则弹出栈顶的运算符和两个数字进行运算,并将结果压入栈中。最后栈中只剩下一个数字,就是表达式的值。
时间复杂度
栈的大小为表达式的长度,所以时间复杂度为 O(n)
Python3 代码
C++ 代码
算法2
(递归) $O(n)$
最简单的方法是使用递归,将表达式分为两个部分,左边和右边,然后递归计算左边和右边的值,然后根据运算符计算结果。
时间复杂度
递归深度为表达式中运算符的个数,时间复杂度为 O(n)
Python3 代码
C++ 代码
算法3
(栈) $O(n)$
时间复杂度
参考文献
Python3 代码
C++ 代码
算法4
(递归) $O(n)$
时间复杂度
参考文献
C++ 代码