栈的应用：实现逆波兰计算器

本文主要是介绍栈的应用：实现逆波兰计算器，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

开篇

本篇文章是学习数据结构过程中的笔记，所以有时代码可能不够完整，会在后续的学习中记录下更完整的代码版本。

思路分析

后缀表达式又称逆波兰表达式，与前缀表达式类似，只是运算符位于操作数之后
举例说明：(3+4)*5-6对应的后缀表达式就是3 4 + 5 * 6 -
后缀表达式的计算机求值过程:
从左至右扫描表达式，遇到数字时，将数字压入栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素和栈顶元素），并将结果入栈；重复上述过程直到表达式的最右端，最后运算得出的值即为表达式的结果。
例如: (3+4)*5-6对应的后缀表达式就是 3 4 + 5 * 6 - ,针对后缀表达式求值步骤如下:

从左至右扫描，将3和4压入堆栈；
遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7压入栈；
将5入栈;
接下来是运算符，因此弹出5和7，计算出57 = 35, 将35入栈;
5.将6入栈;
最后是-运算符，计算出35-6的值，即29，因此得出最终结果

代码实现

package com.zyc.stack;import java.util.ArrayList;
import java.util.List;
import java.util.Stack;public class PolandNotation {public static void main(String[] args) {// (3+4)*5-6  => 3 4 + 5 * 6 -// (30 - 6 ) / 3 * 8 = 64String suffixExpression = "30 6 - 3 / 8 *";// 1. 先将表达式放入到ArrayList中// 2.将ArrayList传递给一个方法，遍历ArrayList配合栈完成计算List<String> list = getListString(suffixExpression);System.out.println("list="+list);int res = calculate(list);System.out.println("运算结构是: " + res);}/*** 完成对逆波兰表达式的计算* 从左至右扫描，将3和4压入堆栈;* 遇到+运算符，因此弹出4和3（4是栈顶元素，3是次顶元素），计算出3+4的值，得7，再将7入栈;* 将5入栈;* 接下来是*运算符，因此弹出5和7，计算出5*7=35, 将35入栈* 将6入栈* 最后是-运算符，计算出35-6的值，即29，因此得出最终结果* @param list* @return*/public static int calculate(List<String> list) {// 创建栈Stack<String> stack = new Stack<>();// 遍历for (String item :list) {// 这里使用正则来取出数if (item.matches("\\d+")) {// 数字入栈stack.push(item);} else {// 如果是运算符，则弹出两个数字，并运算，并把运算结果入栈int num2 = Integer.parseInt(stack.pop());int num1 = Integer.parseInt(stack.pop());int res = 0;if (item.equals("+")) {res = num1 + num2;} else if(item.equals("-")) {res = num1 - num2;} else if(item.equals("*")) {res = num1 * num2;} else if(item.equals("/")) {res = num1 / num2;} else {throw new RuntimeException("运算符错误");}// res入栈stack.push("" + res);}}// 最后留在栈中的就是运算结果return Integer.parseInt(stack.pop());}// 将一个逆波兰表达式，依次将数据和运算符放入到ArrayList中public static List<String> getListString(String suffixExpression) {// 将suffixExpression分割String[] split = suffixExpression.split(" ");List<String> list = new ArrayList<>();for(String ele: split) {list.add(ele);}return list;}
}