题目来源
时间限制:C/C++ 1秒,其他语言2秒空间限制:C/C++ 32M,其他语言64M
题目描述
链接:https://www.nowcoder.com/questionTerminal/22f9d7dd89374b6c8289e44237c70447 来源:牛客网
计算逆波兰式(后缀表达式)的值 运算符仅包含"+","-","*"和"/",被操作数可能是整数或其他表达式 例如:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9↵ ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are+,-,*,/. Each operand may be an integer or another expression.
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9↵ ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
解题思路
思路一
- 利用stack来计算波兰表达式的值,这都是套路
- 程序鲁棒性,考虑各种可能的异常
思路:
- 遇到操作数就出栈,把计算结果入栈
- 计算结果时,stack至少2个数,否则不合法,返回0
- 遇到数字就入栈
- 如果不是操作数,也无法转换为数字,就返回0,这里用try catch
- 结果要合法:
- 如果遍历完成,stack的元素不止1个,说明不合法,返回0
- 当stack元素只有一个的时候,返回结果
来自 @hustZa
思路二
- 逆波兰表达式,用栈求解。
- 需要注意的一点,就是来一个新的符号的时候,将栈中的两个值取出进行操作,再放回栈中。 此时先取出的为num2,后取出的为num1,进行num1 (+-/*) num2 操作
来自 @haorlee
补充
- c++stack(堆栈)是一个容器的改编,它实现了一个先进后出的数据结构(FILO)
CodeBlock Loading...
- atoi()函数将数字格式的字符串转换为整数类型
- cstr()函数返回一个指向正规C字符串的指针常量, 内容与本string串相同. (这是为了与c语言兼容,在c语言中没有string类型,故必须通过string类对象的成员函数cstr()把string 对象转换成c中的字符串样式。)
参考代码
CodeBlock Loading...