栈
一种先进先出的数据结构,是一种线性表,与之相对应的是队列
栈:后进先出(LIFO-last in first out):最后插入的元素最先出来。
队列:先进先出(FIFO-first in first out):最先插入的元素最先出来。
使用栈完成表达式求值的思路
- 通过一个index的值(索引),来遍历我们的表达式
- 如果是一个数字,则直接入数栈
- 如果是一个符号,则进一步判断
- 如果符号栈为空,则直接入栈
- 如果符号栈不为空,则进行比较:如果当前的操作符的优先级小于或者等于栈中的操作符,就需要从数栈中pop出两个数字,从符号栈中pop出一个符号吗,进行运算,将得到的结果入数栈,然后当前的操作符入符号栈;如果当前操作符的优先级大于栈中的操作符,就直接入符号栈
- 当表达式扫描完毕后,就顺序的从数栈和符号栈中pop出相应的数和符号,并运算,将结果压入数栈
- 最后数栈中只有一个数字,就是表达式的结果
代码实现
1 |
参考
- 本文作者: 半度微凉
- 本文链接: http://www.taoweidong.com/2020/05/07/Java数据结构和算法-栈实现表达式求值/
- 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!