本文共 28925 字，大约阅读时间需要 96 分钟。

栈的应用——中缀、后缀(逆波兰)、前缀(波兰)表达式的生成和使用

本篇博文通过一个计算器例子来认识，中缀、后缀、前缀表达式的使用和生成

问题引入

我们需要编写一个能够实现按照运算符号优先级来实现计算的计算器应用，如：输入"1-2*3+6/2-1"，会得到结果"-3"，如何实现？

思路分析和中缀表达式的概念

1. 我们准备两个栈，一个是数字栈(用来存放数字)，另一个是符号栈(用来存放运算符号)；
2. 通过一个 index索引来扫描遍历我们的表达式
   1. 如果我们发现是一个数字，先将当前的数字拼接到一个字符串变量中进行拼串(如70、889、5874、…)，再看后一个元素是什么？
      1. 如果当前扫描得到的表达式的字符的下一位是运算符号，就将上面保存的数字字符串直接入数字栈
      2. 否则，即当前截取的表达式的字符的下一位是数字，不做操作(因为在下一次扫描时就会将其拼接，如2.1所示)
   2. 如果发现是运算符号
      1. 如果当前符号栈为空，就直接入符号栈
      2. 如果符号栈有操作符(不为空)，就判断 当前的符号 与 栈顶指针指向的符号 的优先级：
         1. 如果当前的符号优先级 小于等于 栈顶指针指向的符号优先级，就从数字栈中出栈两个数字，再从符号栈中出栈一个符号，再进行运算得到结果，然后将运算的结果入栈至数字栈;之后再通过2.2.2判断该运算符能否入栈；
         2. 如果当前的符号优先级 大于 栈顶指针指向的符号优先级，就直接将该符号入符号栈;
3. 当遍历表达式完毕，就依次的从数栈弹出两个数字，从符号栈弹出一个符号，再进行计算并得到计算结果，然后将计算结果入栈，一直如此循环，直到符号栈为空时，此时数字栈就只有一个元素，该元素就是表达式的最终计算结果；

感觉看文字有点懵？不存在的，看图解，如下：

通过观察图解你也会发现，这就是中缀表达式，即操作符在操作数的中间，所有的计算通过表达式的运算符优先级顺序进行，我们人类平常手写的表达式(如：1+2-3*6+9、5-2*(3+6)-7、3-2*((4-2)-2/(3-1)-8)+10、…等)； 但是我们一定会发现，中缀表达式虽然便于我们人来观看，但是计算机在处理中缀表达式时是非常痛苦的！因为中缀表达式无论是从左到右、还是从右到左都不能保证运算是有序的(即表达式没有按照运算符的优先级进行排序)，所以上图中(包括下面的中缀计算器代码)我只实现了运算符：+、-、*、/ ，而 )、(这两个运算规则没有实现(太麻烦了！)，那有没有什么比较好的方法来解决？我们可以将中缀表达式转换成后缀表达式或前缀表达式，然后使用后缀表达式或前缀表达式来进行计算！

后缀表达式

后缀表达式：又称为逆波兰表达式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行(不再考虑运算符的优先规则，因此计算机处理十分方便)，如：

• 中缀表达式：1 + 2 - 3 的后缀表达式：1 2 + 3 -
• 中缀表达式：5 + 2 * 3 - 2 / 1 的后缀表达式：5 2 3 * + 2 1 / -
• 中缀表达式：5 + ( 2 - 3 ) * 2 / 3 - 1 的后缀表达式：5 2 3 - 2 3 * / + 1 -
• 中缀表达式：1 * 6 / 5 - 2 * 3 - 6 的后缀表达式：1 6 * 5 / * 2 3 * - 6 -

中缀如何转后缀

该算法思想是固定的，如下：

1. 初始化两个栈：运算符栈s1和储存中间结果的栈s2
2. 从左至右扫描中缀表达式；
3. 遇到操作数时，将其压s2
4. 遇到运算符时，比较其与s1栈顶运算符的优先级：
   1. 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入符号栈
   2. 否则，若优先级比栈顶运算符的高，也将运算符压入s1
   3. 否则，否则，就遍历符号栈s1
      1. 当符号栈的栈顶不为空(即符号栈不为空) 并且 符号栈的栈顶不是"(" 并且符号栈的栈顶优先级 大于等于 当前符号优先级，将s1栈顶的运算符弹出并压入到s2中；
      2. 反之再次转到(4.1)与s1中新的栈顶运算符相比较；
5. 遇到括号时
   1. 如果是左括号“(”，则直接压入s1
   2. 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
6. 重复步骤2至5，直到表达式的最右边(即，将中缀表达式扫描完)
7. 将s1中剩余的运算符依次弹出并压入s2
8. 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

懵了？图解如下：

前缀表达式

前缀表达式：又称为波兰表达式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行(不再考虑运算符的优先规则，因此计算机处理十分方便)，如：

• 中缀表达式：1 + 2 - 3 的前缀表达式：- + 1 2 3
• 中缀表达式：5 + 2 * 3 - 2 / 1 的前缀表达式：- + 5 * 2 3 / 2 1
• 中缀表达式：5 + ( 2 - 3 ) * 2 / 3 - 1 的前缀表达式：- + 5 / * - 2 3 2 3 1
• 中缀表达式：10 * (6 / ( 5 - 3 ) - 2 * 3 - 6) + 4 的前缀表达式：+ * 10 - - / 6 - 5 3 * 2 3 6 4

中缀如何转前缀

中缀表达式转前缀表达式 与 中缀表达式转后缀表达式的算法思想及其相似，只不过是某些地方”取反“而已，如下思想：

1. 初始化两个栈：运算符栈S1和储存中间结果的栈S2；
2. 从右至左扫描中缀表达式；
3. 遇到操作数时，将其压入S2；
4. 遇到运算符时，比较其与S1栈顶运算符的优先级：
   1. 如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈；
   2. 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1；
   3. 否则，就遍历符号栈s1
      1. 当符号栈的栈顶不为空(即符号栈不为空) 并且 符号栈的栈顶不是")" 并且符号栈的栈顶优先级 大于 当前符号优先级，将s1栈顶的运算符弹出并压入到s2中；
      2. 反之再次转到(4.1)与s1中新的栈顶运算符相比较；
5. 遇到括号时：
   1. 如果是右括号“)”，则直接压入S1；
   2. 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃；
6. 重复步骤2至5，直到表达式的最左边；
7. 将S1中剩余的运算符依次弹出并压入S2；
8. 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。

因为及其与转后缀的思想及其相似，所以这里我们就不列举向上面一样复杂的图示了，如下图示：

编码

自定义一个栈结构

我们通过分析，要完成上述的计算器需求，不管使用什么方法，都涉及到了大量的压栈、弹栈、等栈操作，因此这里我们为了更好的学习和方便代码的调试，我们自定义一个栈结构，如下：

package edu.hebeu.calculator;import java.lang.reflect.Array;/** * 使用数组自定义的栈结构 * @author 13651 * * @param 
   
     数组的类型 */public class MyStack
    
      {
   		/**	 * 存放栈数据的数组	 */	private T[] array;		/**	 * 容量	 */	private int capacity;		/**	 * 栈顶指针	 */	private int top = -1;		/**	 * 构造器	 * @param c 数组泛型的字节码对象	 * @param capacity 数组容量	 */	public MyStack(Class
     
       c, int capacity) {
   		this.capacity = capacity;		array = (T[]) Array.newInstance(c, capacity);//		array = (T[]) new Object[capacity]; // 或者使用该方法	}		/**	 * 入栈	 * @param data	 */	public void push(T data) {
   		if(isFull()) {
   			System.err.println("栈满！");			return;		}//		System.out.println("入栈：" + data);		array[++top] = data;	}		/**	 * 出栈	 * @return	 */	public T pop() {
   		if(isEmpty()) {
   			System.err.println("栈空！");			return null;		}//		System.out.println("出栈：" + array[top]);		return array[top--];	}		/**	 * 该方法用来获取栈顶元素的值(注意是查看，不是弹栈)	 * @return	 */	public T seeTop() {
   		if(top == -1) {
   			return null;		}		return array[top];	}		/**	 * 该方法用来获取当前栈内的元素个数	 * @return	 */	public int size() {
   		return top + 1;	}		/**	 * 判断栈是否空	 * @return	 */	public boolean isEmpty() {
   		return top == -1;	}		/**	 * 判断栈是否满	 * @return	 */	public boolean isFull() {
   		return top == capacity - 1;	}		/**	 * 打印栈内元素	 */	public void show() {
   		if(isEmpty()) {
   			System.err.println("栈空！");			return;		}		for(int i = top; i >= 0; i--) {
   			System.out.println(array[i]);		}	}}
     
    
   

中缀表达式解决计算器需求

我们首先从上述的问题引入出来使用中缀表达式解决该问题，如下编码：

package edu.hebeu.calculator;/** * 这个类用来模拟计算器(中缀表达式实现) *  * 中缀表达式：即操作符在操作数的中间，所有的计算通过表达式的运算符优先级顺序进行， * 就是我们经常写的如：a+b-c*(d+f)、a+b、c-h、... *  * 思路分析： * 	1、我们准备两个栈，一个是数字栈(用来存放数字)，另一个是符号栈(用来存放运算符号) * 	2、通过一个 index索引来扫描遍历我们的表达式 * 		2.1、如果我们发现是一个数字，就先看一下后一个元素是什么？ * 			2.1.1、如果是数字，先将当前的数字拼接到一个字符串变量中进行拼串(如70、889、5874、...) * 				2.1.1.1、如果当前扫描得到的表达式的字符的下一位是运算符号，就将上面保存的数字字符串直接入数字栈 * 				2.1.1.2、否则，即当前截取的表达式的字符的下一位是数字，不做操作(因为在下一次扫描时就会将其拼接，如3.1所示) * 		2.2、如果发现是运算符号 * 			2.2.1、如果当前符号栈为空，就直接入符号栈 * 			2.2.2、如果符号栈有操作符(不为空)，就判断 当前的符号 与 栈顶指针指向的符号 的优先级： * 				2.2.2.1、如果当前的符号优先级 小于等于 栈顶指针指向的符号优先级，就从数字栈中出栈两个数字，再从符号栈 * 				中出栈一个符号，再进行运算得到结果，然后将运算的结果入栈至数字栈;之后再通过2.2.2判断该运算符能否入栈； * 				2.2.2.2、如果当前的符号优先级 大于 栈顶指针指向的符号优先级，就直接将该符号入符号栈 * 	3、当遍历表达式完毕，就依次的从数栈弹出两个数字，从符号栈弹出一个符号，再进行计算并得到计算结果，然后将计算结果入栈， * 	一直如此循环，直到符号栈为空时，此时数字栈就只有一个元素，该元素就是表达式的最终计算结果； * 	 * 	中缀表达式虽然便于我们人来观看，但是计算机在处理中缀表达式时是非常痛苦的！因为中缀表达式无论是从左到右、还是从右到左 * 都不能保证运算是有序的(即表达式没有按照运算符的优先级进行排序)，所以本例中我只实现了运算符：+ - * / ，而 ) ( 这两个运 * 算规则没有实现(太麻烦了！)，那有没有什么比较好的方法来解决？我们可以将中缀表达式转换成后缀表达式或前缀表达式，然后使用后缀 * 表达式或前缀表达式来进行计算！ *  * 	前缀(波兰)表达式：指的是不包含括号，运算符放在两个运算对象的前面，严格从右向左进行，所有的计算按运算符出现的 * 顺序(不再考虑运算符的优先规则，因此计算机处理十分方便) *  * 	后缀(逆波兰)表达式：指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行(不 * 再考虑运算符的优先规则，因此计算机处理十分方便) *  * @author 13651 * */public class InfixCalculator {
   	/**	 * 数字栈和符号栈的容量：1000	 */	private static final Integer STACK_CAPACITY = 1000;		/**	 * 数字栈，底层是Float类型的数组	 */	private static final MyStack
   
     NUMBER_STACK = new MyStack<>(Float.class, STACK_CAPACITY);		/**	 * 符号栈，底层是Character类型的数组	 */	private static final MyStack
    
      SYMBOL_STACK = new MyStack
     
      (Character.class, STACK_CAPACITY);		/**	 * 需要计算的表达式	 */	private String infixExpression;		/**	 * 指针，用来指向 当前操作表达式的那个位置(那个字符)，默认为0，即默认操作第一个字符	 */	private int pointer = 0;		/**	 * 该字符串用来保存每次截取表达式获得的字符(用来进行拼串，防止多位数字参与计算时被拆分成单个的数字入	 * 栈而导致计算失败)，如：80、948、-7、-89、...等	 */	String number = "";		/**	 * 构造器	 * @param infixExpression 进行计算操作的中缀表达式	 */	public InfixCalculator(String infixExpression) {
   		this.infixExpression = infixExpression.replaceAll(" ", ""); // 将传入的中缀表达式的所有空格去除	}		/**	 * 该方法用来计算并返回表达式的值	 * @return	 */	public Float calculationExpression() {
   		while(true) {
   			/* TODO 每次将表达式从pointer截取到pointer+1个字符(即截取一个字符)，并通过charAt(0)将截取到			 * 的一个字符的字符串转换为字符类型			 */			Character expressionItem = infixExpression.substring(pointer, pointer + 1).charAt(0);//			System.out.println(">>>" + expressionItem.toString());			// TODO 如果当前的截取的表达式的字符为符号			if(isSymbol(expressionItem)) {
   				// TODO 如果符号栈为空				if(SYMBOL_STACK.isEmpty()) {
   					// TODO 直接入符号栈					SYMBOL_STACK.push(expressionItem);				}				// TODO 程序执行到此，说明符号栈不为空				// TODO 如果当前的符号的优先级 小于等于 符号栈顶指向符号的优先级				else if(priority(expressionItem) <= priority(SYMBOL_STACK.seeTop())) {
   					/* TODO 调用bombStackCalculation()方法，该方法会从数字栈中出栈两个数字，再从符号栈					 * 中出栈一个符号，再进行运算得到结果，然后将运算的结果入栈至数字栈，这样做为了保证					 * 符号栈中始终没有低优先级的符号在高优先级符号之上的情况，以保证的高优先级的符号 始					 * 终领先于 低优先级的符号 执行					 */					bombStackCalculation();					/* TODO 结束掉本次循环(让pointer保持不变，即还是截取表达式的该位置，此时进入下一循环					 * 继续判断该符号能否入栈，这样做是为了保证符号栈中始终没有同优先级的符号情况，以解决					 * 有 -x 时的负数计算错误问题)					 */					continue;				} 				// TODO 否则，即当前的符号优先级 大于 栈顶指针指向的符号优先级				else if(priority(expressionItem) > priority(SYMBOL_STACK.seeTop())) {
   					// TODO 直接将该符号入符号栈					SYMBOL_STACK.push(expressionItem);				}			}			// TODO 否则，即如果是数字			else {
   				// TODO 先将当前的数字保存到一个字符串变量中进行拼串(如70、889、5874、...)				number += expressionItem;				// TODO 如果当前截取的表达式的字符是表达式的最后一位				if(pointer == infixExpression.length() - 1) {
   					// TODO 将当前的数字入栈					NUMBER_STACK.push(Float.parseFloat(number));					number = ""; // 将保存数字的字符串至空				}				// TODO 如果当前截取的表达式的字符的下一位是运算符号				else if(isSymbol(infixExpression.substring(pointer + 1, pointer + 1 + 1).charAt(0))) {
   					// TODO 将当前的数字入栈					NUMBER_STACK.push(Float.parseFloat(number));					number = ""; // 将保存数字的字符串至空				}			}			// 扫描的指针后移			pointer++;			// TODO 如果pointer 大于等于 表达式的长度，即表达式遍历完毕(因为pointer是从0开始的，索引pointer 等于 表达式的长度 - 1时就是表达式的最后位置，如果pointer等于表达式的长度，那么表达式一定已经遍历完了)			if(pointer >= infixExpression.length()) {
   				break;			}					}		// TODO 程序执行到此，说明表达式遍历完毕		while(true) {
   			// TODO 如果符号栈为空，此时数字栈就只剩一个元素了(即为运算的结果)			if(SYMBOL_STACK.isEmpty()) {
   				break;			}			/* TODO 调用bombStackCalculation()方法，该方法就从数字栈中出栈两个数字，再从符号栈			 * 中出栈一个符号，再进行运算得到结果，然后将运算的结果入栈至数字栈			 */			bombStackCalculation();		}		return NUMBER_STACK.pop();	}		/**	 * 该方法就从数字栈中出栈两个数字，再从符号栈中出栈一个符号，再进行运算得到结果，然后将运算的结果入栈	 * 至数字栈	 * @return	 */	public void bombStackCalculation() {
   		Float res = null; // 该变量用来保存计算的结果		// TODO 从符号栈弹出一个符号元素		Character symbol = SYMBOL_STACK.pop();		// TODO 从数字栈弹出两个数组元素(即弹出栈顶元素和次顶元素)，如下		Float topNumber = NUMBER_STACK.pop(); // 栈顶元素		Float secondaryNumber = NUMBER_STACK.pop(); // 次顶元素		// TODO 判断符号，通过符号来计算		switch(symbol) {
   			case '*'://				System.out.printf("-->%f * %f = %f\n", secondaryNumber, topNumber, secondaryNumber * topNumber);				res = secondaryNumber * topNumber;				break;			case '/'://				System.out.printf("-->%f / %f = %f\n", secondaryNumber, topNumber, secondaryNumber / topNumber);				res = secondaryNumber / topNumber;				break;			case '+'://				System.out.printf("-->%f + %f = %f\n", secondaryNumber, topNumber, secondaryNumber + topNumber);				res = secondaryNumber + topNumber;				break;			case '-'://				System.out.printf("-->%f - %f = %f\n", secondaryNumber, topNumber, secondaryNumber - topNumber);				res = secondaryNumber - topNumber;				break;			default:				res = 0F;				break;		}		// TODO 将计算的结果入栈至数字栈		NUMBER_STACK.push(res);	}		/**	 * 该方法用来表达式的某个字符是否为符号	 * @param expression_item 表达式的某个字符	 * @return	 */	public boolean isSymbol(Character expression_item) {
   		return expression_item.equals('+') || expression_item.equals('-') || 				expression_item.equals('*') || expression_item.equals('/');	}		/**	 * 该方法用来判断符号的优先级	 * @param symbol	 * @return	 */	public int priority(Character symbol) {
   		if(symbol.equals('*') || symbol.equals('/')) {
   			return 2;		} else if(symbol.equals('+') || symbol.equals('-')) {
   			return 1;		}		return -1;	}	}
     
    
   

中缀转后缀和前缀

我们之前一直说，中缀表达式适合人来阅读，但是在编码时处理却非常麻烦，特别是括号问题；而后缀和前缀表达式编码时容易处理，但是人却不方便阅读和编写；所以，这里我们定义一个工具类，内包含将中缀表达式字符串的拆分成List<String>集合的方法、List<String>类型的中缀表达式转换成List<String>类型的后缀和前缀表达式方法、将List<String>类型的表达式转换成标准的表达式字符串的方法、等等，如下：

package edu.hebeu.calculator;import java.util.ArrayList;import java.util.List;public class Util {
   		/**	 * 该方法 通过将中缀表达式字符串 拆分成 List
   
    类型的中缀表达式项集合	 * 如：中缀表达式 2 + ((3 - 5) * 6 - 1) - 8   变成   List
    
     {2, +, (, (, 3, -, 5, ), *, 6, -, 1, ), -, 8}	 * @param infixExpression String类型的中缀表达式	 * @return 拆分成的List
     
      集合	 */	public static List
      
        getInfixExpressionList(String infixExpression) {
   //		System.out.println("infix -->" + infixExpression);		List
       
         infixExpressionList = new ArrayList<>();		// TODO 用来扫描 String类型的指针，默认为0		int pointer = 0;		// TODO 用来保存当前扫描String类型的中缀表达式得到的字符		char infixExpressionItem = ' ';		// TODO 用来保存数字，实现多位数的拼接		String number = "";		// TODO 如果扫描的指针 小于 String类型的中缀表达式的长度(没有扫描完)		while(pointer < infixExpression.length()) {
   			// TODO 获取扫描指针指向的 String类型的中缀表达式的元素			infixExpressionItem = infixExpression.charAt(pointer);			// TODO 如果本次扫描得到的元素是' '			if(infixExpressionItem == ' ') {
   				// 扫描的指针后移				pointer++;				// 结束本次循环，不做任何处理(即将' '值除去)				continue;			}			/* TODO 如果扫描得到的元素 不是数字			 * ASII码：'0'(48) ~ '9'(57)   '.'(46)			 */			else if((infixExpressionItem < 48 || infixExpressionItem > 57) && 					infixExpressionItem != 46) {
   				// TODO 将扫描得到的元素加入到List
        
         集合中 infixExpressionList.add("" + infixExpressionItem); pointer++; } // TODO 否则，即是数字 else { number = ""; // 将存放多位数的变量置为"" /* TODO 当pointer扫描指针 小于 String类型的中缀表达式长度(即没有遍历完)， * 并且扫描得到的元素 是数字或者小数点 * ASII码：'0'(48) ~ '9'(57) '.'(46) */ while(pointer < infixExpression.length() && ((infixExpression.charAt(pointer) >= 48 && infixExpression.charAt(pointer) <= 57) || infixExpression.charAt(pointer) == 46)) { // TODO 将扫描得到的元素拼接到 number变量上(拼接多位数使用) number += infixExpression.charAt(pointer); pointer++;// System.out.println("num ---> " + number); } // TODO 程序执行到此说明多位数已经拼接，那么此时应该将多位数加入List
         
          集合 infixExpressionList.add(number);// System.out.println("number = " + number); } }// System.out.println();System.out.println(); return infixExpressionList; } /** * 后缀表达式：又称为逆波兰表达式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符 * 出现的顺序，严格从左向右进行(不再考虑运算符的优先规则，因此计算机处理十分方便)，如： * 中缀表达式：1 + 2 - 3 的后缀表达式：1 2 + 3 - * 中缀表达式：5 + 2 * 3 - 2 / 1 的后缀表达式：5 2 3 * + 2 1 / - * 中缀表达式：5 + ( 2 - 3 ) * 2 / 3 - 1 的后缀表达式：5 2 3 - 2 3 * / + 1 - * 中缀表达式：1 * 6 / 5 - 2 * 3 - 6 的后缀表达式：1 6 * 5 / * 2 3 * - 6 - * * 该方法用来将 List
          
           类型的中缀表达式集合 转换成 List
           
            类型的后缀表达式集合(即中缀表达式 转后缀表达式)，思路如下： 1、初始化两个栈：运算符栈s1和储存中间结果的栈s2 2、从左至右扫描中缀表达式； 3、遇到操作数时，将其压s2 4、遇到运算符时，比较其与s1栈顶运算符的优先级： 4.1、如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入符号栈 4.2、否则，若优先级比栈顶运算符的高，也将运算符压入s1 4.3、否则，否则，就遍历符号栈s1 4.3.1、当符号栈的栈顶不为空(即符号栈不为空) 并且 符号栈的栈顶不是"(" 并且符号栈的栈顶优 先级 大于等于 当前符号优先级，将s1栈顶的运算符弹出并压入到s2中； 4.3.2、反之再次转到(4.1)与s1中新的栈顶运算符相比较； 5、遇到括号时 5.1、如果是左括号“(”，则直接压入s1 5.2、如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃 6、重复步骤2至5，直到表达式的最右边(即，将中缀表达式扫描完) 7、将s1中剩余的运算符依次弹出并压入s2 8、依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式 * * @param infixExpressionList List
            
             类型的中缀表达式集合 * @return 转换好的 List
             
              类型的后缀表达式集合 */ public static List
              
                getSuffixExpressionList(List
               
                 infixExpressionList) { List
                
                  suffixExpressionList = new ArrayList
                 
                  (); // 用来存放 转换好的 List
                  
                   类型的后缀表达式集合 // TODO 1、初始化两个栈：运算符栈s1和储存中间结果的栈s2 MyStack
                   
                     symbolStack = new MyStack<>(String.class, 1000); // 符号栈 MyStack
                    
                      midResStack = new MyStack<>(String.class, 1000); // 存放中间结果的栈 // TODO 2、从左到右扫描中缀表达式 for(String infixExpressionItem : infixExpressionList) { /* TODO 3、遇到操作数时，将其压s2； * \\d+：是正则表达式，表示为数字 * (\\d+\\.\\d+)：是正则表达式，表示为带小数点数字 */ if(infixExpressionItem.matches("\\d+") || infixExpressionItem.matches("(\\d+\\.\\d+)")) { midResStack.push(infixExpressionItem); // 将操作数压入中间结果栈 } // TODO 5、遇到括号时，5.1、如果是左括号“(”，则直接压入s1 else if(infixExpressionItem.equals("(")) { symbolStack.push(infixExpressionItem); // 将 "(" 压入符号栈 } // TODO 5.2、如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃 else if(infixExpressionItem.equals(")")) { while(!symbolStack.seeTop().equals("(")) { // 栈顶元素不为 "("时 midResStack.push(symbolStack.pop()); // 将符号栈弹栈出的元素 压入 中间结果栈 } symbolStack.pop(); // 程序执行到此处，栈顶的元素必为 "("，那么我们将该元素弹出，达到去除括号 } /*程序执行到此，说明当前扫描到的中缀表达式项 是运算符*/ // TODO 4、遇到运算符时，比较其与s1栈顶运算符的优先级： else { while(true) { // TODO 4.1、如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入符号栈 if(symbolStack.isEmpty() || symbolStack.seeTop().equals("(")) { symbolStack.push(infixExpressionItem); // 直接将此运算符入符号栈 break; } // TODO 4.2、否则，若优先级比栈顶运算符的高，也将运算符压入s1 else if(priority(infixExpressionItem.charAt(0)) > priority(symbolStack.seeTop().charAt(0))) { symbolStack.push(infixExpressionItem); // 将运算符压入 符号栈 break; } /* TODO 4.3、否则，就遍历符号栈s1 * * 4.3.1、当符号栈的栈顶不为空(即符号栈不为空) 并且 符号栈的栈顶不是"(" * 并且符号栈的栈顶优先级 大于等于 当前符号优先级，将s1栈顶的运算符弹出 * 并压入到s2中； * * 4.3.2、反之再次转到(4.1)与s1中新的栈顶运算符相比较； * */ while(!symbolStack.isEmpty() && !symbolStack.seeTop().equals("(") && priority(infixExpressionItem.charAt(0)) <= priority(symbolStack.seeTop().charAt(0))) { midResStack.push(symbolStack.pop()); // 将符号栈弹出的元素 压入 中间结果栈 } } } // TODO 6、重复步骤2至5，直到表达式的最右边(即，将中缀表达式集合遍历完(中缀表达式扫描完)) } // TODO 7、将s1中剩余的运算符依次弹出并压入s2 while(symbolStack.size() != 0) { midResStack.push(symbolStack.pop()); // 将符号栈弹出的元素 压入 中间结果栈 } // TODO 8、依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式 List
                     
                       tmp = new ArrayList
                      
                       (); while(midResStack.size() != 0) { tmp.add(midResStack.pop()); // 依次弹出中间结果栈的元素 并加入 List集合中 } for(int i = tmp.size() - 1; i >= 0; i--) { // 将List集合内的元素倒置 suffixExpressionList.add(tmp.get(i)); } return suffixExpressionList; } /** * 前缀表达式：又称为波兰表达式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出 * 现的顺序，严格从左向右进行(不再考虑运算符的优先规则，因此计算机处理十分方便)，如： * 中缀表达式：1 + 2 - 3 的前缀表达式：- + 1 2 3 * 中缀表达式：5 + 2 * 3 - 2 / 1 的前缀表达式：- + 5 * 2 3 / 2 1 * 中缀表达式：5 + ( 2 - 3 ) * 2 / 3 - 1 的前缀表达式：- + 5 / * - 2 3 2 3 1 * 中缀表达式：10 * (6 / ( 5 - 3 ) - 2 * 3 - 6) + 4 的前缀表达式：+ * 10 - - / 6 - 5 3 * 2 3 6 4 * * 该方法用来将 List
                       
                        类型的中缀表达式集合 转换成 List
                        
                         类型的前缀表达式集合(即中缀表达式 转前缀表达式)，思路如下： 1、初始化两个栈：运算符栈S1和储存中间结果的栈S2； 2、从右至左扫描中缀表达式； 3、遇到操作数时，将其压入S2； 4、遇到运算符时，比较其与S1栈顶运算符的优先级： 4.1、如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈； 4.2、否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1； 4.3、否则，就遍历符号栈s1 4.3.1、当符号栈的栈顶不为空(即符号栈不为空) 并且 符号栈的栈顶不是")" 并且符号栈的栈顶优先 级 大于 当前符号优先级，将s1栈顶的运算符弹出并压入到s2中； 4.3.2、反之再次转到(4.1)与s1中新的栈顶运算符相比较； 5、遇到括号时： 5.1、如果是右括号“)”，则直接压入S1； 5.2、如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃； 6、重复步骤2至5，直到表达式的最左边； 7、将S1中剩余的运算符依次弹出并压入S2； 8、依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。 * * @param infixExpressionList List
                         
                          类型的中缀表达式集合 * @return 转换好的 List
                          
                           类型的前缀表达式集合 */ public static List
                           
                             getPrefixExpressionList(List
                            
                              infixExpressionList) { List
                             
                               prefixExpressionList = new ArrayList
                              
                               (); // 用来存放 转换好的 List
                               
                                类型的后缀表达式集合 // TODO 1、初始化两个栈：运算符栈s1和储存中间结果的栈s2 MyStack
                                
                                  symbolStack = new MyStack<>(String.class, 1000); // 符号栈 MyStack
                                 
                                   midResStack = new MyStack<>(String.class, 1000); // 存放中间结果的栈 // TODO 先将中缀表达式反序 List
                                  
                                    reverseInfixExpressionList = new ArrayList
                                   
                                    (); for(int i = infixExpressionList.size() - 1; i >= 0; i--) { reverseInfixExpressionList.add(infixExpressionList.get(i)); }// System.out.println("infixExpressionList -> " + infixExpressionList);// System.out.println("reverseInfixExpressionList -> " + reverseInfixExpressionList); // TODO 2、遍历存放反序后的中缀表达式项的集合(从右到左扫描中缀表达式) for(String infixExpressionItem : reverseInfixExpressionList) { /* TODO 3、遇到操作数时，将其压s2； * \\d+：是正则表达式，表示为数字 * (\\d+\\.\\d+)：是正则表达式，表示为带小数点数字 */ if(infixExpressionItem.matches("\\d+") || infixExpressionItem.matches("(\\d+\\.\\d+)")) { midResStack.push(infixExpressionItem); // 将操作数压入中间结果栈 } // TODO 5、遇到括号时，5.1、如果是右括号“)”，则直接压入s1 else if(infixExpressionItem.equals(")")) { symbolStack.push(infixExpressionItem); // 将 ")" 压入符号栈 } // TODO 5.2、如果是左括号“(”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃 else if(infixExpressionItem.equals("(")) { // System.out.println("===>" + symbolStack.seeTop()); while(!symbolStack.seeTop().equals(")")) { // 栈顶元素不为 ")"时 midResStack.push(symbolStack.pop()); // 将符号栈弹栈出的元素 压入 中间结果栈 } symbolStack.pop(); // 程序执行到此处，栈顶的元素必为 ")"，那么我们将该元素弹出，达到去除括号 } /*程序执行到此，说明当前扫描到的中缀表达式项 是运算符*/ // TODO 4、遇到运算符时，比较其与s1栈顶运算符的优先级： else { while(true) { // TODO 4.1、如果s1为空，或栈顶运算符为左括号“)”，则直接将此运算符入符号栈 if(symbolStack.isEmpty() || symbolStack.seeTop().equals(")")) { symbolStack.push(infixExpressionItem); // 直接将此运算符入符号栈 break; } // TODO 4.2、否则，若优先级比栈顶运算符的高或相等，也将运算符压入s1 else if(priority(infixExpressionItem.charAt(0)) >= priority(symbolStack.seeTop().charAt(0))) { symbolStack.push(infixExpressionItem); // 将运算符压入 符号栈 break; } /* TODO 4.3、否则，就遍历符号栈s1 * * 4.3.1、当符号栈的栈顶不为空(即符号栈不为空) 并且 符号栈的栈顶不是")" * 并且符号栈的栈顶优先级 大于 当前符号优先级，将s1栈顶的运算符弹出 * 并压入到s2中； * * 4.3.2、反之再次转到(4.1)与s1中新的栈顶运算符相比较； * */ while(!symbolStack.isEmpty() && !symbolStack.seeTop().equals(")") && priority(infixExpressionItem.charAt(0)) < priority(symbolStack.seeTop().charAt(0))) { midResStack.push(symbolStack.pop()); // 将符号栈弹出的元素 压入 中间结果栈 } } } // TODO 6、重复步骤2至5，直到表达式的最右边(即，将中缀表达式集合遍历完(中缀表达式扫描完)) } // TODO 7、将s1中剩余的运算符依次弹出并压入s2 while(symbolStack.size() != 0) { midResStack.push(symbolStack.pop()); // 将符号栈弹出的元素 压入 中间结果栈 } // TODO 8、依次弹出s2中的元素并输出，结果即为中缀表达式对应的前缀表达式。 while(midResStack.size() != 0) { prefixExpressionList.add(midResStack.pop()); // 依次弹出中间结果栈的元素 并加入 List集合中 }// System.out.println("prefixExpressionList -> " + prefixExpressionList); return prefixExpressionList; } /** * 该方法通过 存放在List
                                    
                                     类型集合中的表达式 获取 字符串类型的表达式 * @param expressionList * @return */ public static String stringExpression(List
                                     
                                       expressionList) { StringBuilder expression = new StringBuilder(); for(String expressionItem : expressionList) { expression.append(expressionItem); expression.append(" "); } return expression.toString(); } /** * 该方法用来决定运算符(+ - * /)的优先级 * @param symbol * @return */ private static int priority(Character symbol) { if(symbol.equals('*') || symbol.equals('/')) { return 2; } else if(symbol.equals('+') || symbol.equals('-')) { return 1; } return -1; }}
                                     
                                    
                                   
                                  
                                 
                                
                               
                              
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

后缀表达式解决计算器需求

我们之前一直说后缀表达式在编码处理时特别方便，有多方便？思路如下：

从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果; 代码如下：

package edu.hebeu.calculator;/** * 这个类用来模拟计算器(后缀表达式实现) *  * 思路分析： * 	从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应 * 的计算（次顶元素 和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式 * 的结果 *  * @author 13651 * */public class SufixCalculator {
   	/**	 * 数字栈和符号栈的容量：1000	 */	private static final Integer STACK_CAPACITY = 1000;		/**	 * 用来辅助逆波兰表达式计算的栈	 */	private static final MyStack
   
     STACK = new MyStack
    
     (String.class, STACK_CAPACITY);		/**	 * 需要存放 进行计算的后缀表达式的每个元素的String[]类型的数组	 */	private String[] suffixExpressionItems;		/**	 * 构造器	 * @param infixExpression 进行计算操作的后缀表达式	 */	public SufixCalculator(String suffixExpression) {
   		this.suffixExpressionItems = suffixExpression.split(" "); // 将传入的后缀表达式的按照,进行切割	}		/**	 * 该方法用来计算并返回表达式的值，思路分析：	 * 	从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相	 * 应的计算（次顶元素 和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表	 * 达式的结果	 * @return	 */	public Float calculationExpression() {
   //		System.out.println("suffixExpressionItems --> " + suffixExpressionItems);		// TODO 遍历存放后缀表达式项的集合(从左到右扫描表达式)		for(String suffixExpressionItem : suffixExpressionItems) {
   			// TODO 如果是运算符号			if(isSymbol(suffixExpressionItem)) {
   				/* TODO 调用bombStackCalculation()方法，				 * 该方法是从栈中弹出两个元素(栈顶元素和次顶元素)，并通过符号的不同计算这两个元素，然后将计				 * 算的结果放入栈中				 */				bombStackCalculation(suffixExpressionItem);			}			// TODO 否则，即是数字			else {
   				// TODO 将数字推入栈				STACK.push(suffixExpressionItem);			}		}		return Float.parseFloat(STACK.pop());	}		/**	 * 该方法是从栈中弹出两个元素(栈顶元素和次顶元素)，并通过符号的不同计算这两个元素，然后将计算的结果放	 * 入栈中	 * @param symbol	 */	public void bombStackCalculation(String symbol) {
   		Float res = null; // 该变量用来保存计算的结果		// TODO 从数字栈弹出两个数组元素(即弹出栈顶元素和次顶元素)，如下		Float topNumber = Float.parseFloat(STACK.pop()); // 栈顶元素		Float secondaryNumber = Float.parseFloat(STACK.pop()); // 次顶元素		// TODO 判断符号，通过符号来计算		switch(symbol) {
   			case "*":	//			System.out.printf("-->%f * %f = %f\n", secondaryNumber, topNumber, secondaryNumber * topNumber);				res = secondaryNumber * topNumber;				break;			case "/":	//			System.out.printf("-->%f / %f = %f\n", secondaryNumber, topNumber, secondaryNumber / topNumber);				res = secondaryNumber / topNumber;				break;			case "+":	//			System.out.printf("-->%f + %f = %f\n", secondaryNumber, topNumber, secondaryNumber + topNumber);				res = secondaryNumber + topNumber;				break;			case "-":	//			System.out.printf("-->%f - %f = %f\n", secondaryNumber, topNumber, secondaryNumber - topNumber);				res = secondaryNumber - topNumber;				break;			default:				res = 0F;				break;		}		// TODO 将计算的结果入栈		STACK.push(String.valueOf(res));	}		/**	 * 该方法用来表达式的某个字符是否为符号	 * @param expression_item 表达式的某个字符	 * @return	 */	public boolean isSymbol(String expression_item) {
   		return expression_item.equals("+") || expression_item.equals("-") || 				expression_item.equals("*") || expression_item.equals("/");	}	}
    
   

前缀表达式解决计算器需求

我们前面也说过，前缀表达式也非常方便编码的处理，如下思路：

从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 和 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果

package edu.hebeu.calculator;/** * 这个类用来模拟计算器(前缀表达式实现) *  * 思路分析： * 	从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应 * 的计算（栈顶元素 和 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式 * 的结果 *  * @author 13651 * */public class PrefixCalculator {
   	/**	 * 数字栈和符号栈的容量：1000	 */	private static final Integer STACK_CAPACITY = 1000;		/**	 * 用来辅助逆波兰表达式计算的栈	 */	private static final MyStack
   
     STACK = new MyStack
    
     (String.class, STACK_CAPACITY);		/**	 * 需要存放 进行计算的后缀表达式的每个元素的String[]类型的数组	 */	private String[] prefixExpressionItems;		/**	 * 构造器	 * @param infixExpression 进行计算操作的后缀表达式	 */	public PrefixCalculator(String prefixExpression) {
   		String[] tmp = prefixExpression.split(" "); // 将传入的前缀表达式的按照空格进行切割		// TODO 将存储前缀表达式的 tmp数组变量 倒置到prefixExpression		int index = 0;		this.prefixExpressionItems = new String[tmp.length];		for(int i = tmp.length - 1; i >= 0; i--) {
   			this.prefixExpressionItems[index++] = tmp[i];		}	}		/**	 * 该方法用来计算并返回表达式的值，思路分析：	 * 	从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应	 * 的计算（栈顶元素 和 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式	 * 的结果	 * @return	 */	public Float calculationExpression() {
   		// TODO 遍历存放前缀表达式项的集合(因为在构造器内已经进行了倒置处理，所以此时是从右到左扫描表达式)		for(String prefixExpressionItem : prefixExpressionItems) {
   			// TODO 如果是运算符号			if(isSymbol(prefixExpressionItem)) {
   				/* TODO 调用bombStackCalculation()方法，				 * 该方法是从栈中弹出两个元素(栈顶元素和次顶元素)，并通过符号的不同计算这两个元素，然后将计				 * 算的结果放入栈中				 */				bombStackCalculation(prefixExpressionItem);			}			// TODO 否则，即是数字			else {
   				// TODO 将数字推入栈				STACK.push(prefixExpressionItem);			}		}		return Float.parseFloat(STACK.pop());	}		/**	 * 该方法是从栈中弹出两个元素(栈顶元素和次顶元素)，并通过符号的不同计算这两个元素，然后将计算的结果放	 * 入栈中	 * @param symbol	 */	public void bombStackCalculation(String symbol) {
   		Float res = null; // 该变量用来保存计算的结果		// TODO 从数字栈弹出两个数组元素(即弹出栈顶元素和次顶元素)，如下		Float topNumber = Float.parseFloat(STACK.pop()); // 栈顶元素		Float secondaryNumber = Float.parseFloat(STACK.pop()); // 次顶元素		// TODO 判断符号，通过符号来计算		switch(symbol) {
   			case "*":	//			System.out.printf("-->%f * %f = %f\n", secondaryNumber, topNumber, secondaryNumber * topNumber);				res = topNumber * secondaryNumber;				break;			case "/":	//			System.out.printf("-->%f / %f = %f\n", secondaryNumber, topNumber, secondaryNumber / topNumber);				res = topNumber / secondaryNumber;				break;			case "+":	//			System.out.printf("-->%f + %f = %f\n", secondaryNumber, topNumber, secondaryNumber + topNumber);				res = topNumber + secondaryNumber;				break;			case "-":	//			System.out.printf("-->%f - %f = %f\n", secondaryNumber, topNumber, secondaryNumber - topNumber);				res = topNumber - secondaryNumber;				break;			default:				res = 0F;				break;		}		// TODO 将计算的结果入栈		STACK.push(String.valueOf(res));	}		/**	 * 该方法用来表达式的某个字符是否为符号	 * @param expression_item 表达式的某个字符	 * @return	 */	public boolean isSymbol(String expression_item) {
   		return expression_item.equals("+") || expression_item.equals("-") || 				expression_item.equals("*") || expression_item.equals("/");	}}
    
   

测试类

为了方便上面代码的使用测试和程序的连贯性，创建如下的测试类：

package edu.hebeu.calculator;import java.util.List;import java.util.Scanner;// 800 - 60 - ( 50 / 10 * 2 - 30 / ( 20 - 15 ) - 70 ) + 100 // "2-3*(5-2/(3-1)-8)+10"public class Test {
   	private static final Scanner SCANNER = new Scanner(System.in);		public static void main(String[] args) {
   		while(true) {
   			System.out.println("点击回车开始程序...");			SCANNER.nextLine(); // 这句话是为了防止 String infixExpression = SCANNER.nextLine();读取到/n，导致没有第二次循环以后不能输入表达式			System.out.println();System.out.println();			System.out.println("支持符号：+ - * / ) (");			System.out.print("请输入表达式(中缀表达式)："); String infixExpression = SCANNER.nextLine();						List
   
     infixExpressionList = Util.getInfixExpressionList(infixExpression); // 通过输入的字符串将中缀表达式解析至List
    
     集合			List
     
       sufixExpressionList = Util.getSuffixExpressionList(infixExpressionList); // 通过 中缀表达式的List
      
       集合 得到 后缀表达式集合			List
       
         prefixExpressionList = Util.getPrefixExpressionList(infixExpressionList); // 通过 中缀表达式的List
        
         集合 得到 前缀表达式集合 System.out.println();System.out.println(); System.out.println("中缀表达式：" + Util.stringExpression(infixExpressionList)); System.out.println("后缀表达式：" + Util.stringExpression(sufixExpressionList)); System.out.println("前缀表达式：" + Util.stringExpression(prefixExpressionList)); System.out.println();System.out.println(); System.out.println("请选择您测试的计算器类型"); System.out.println("中缀计算器(infix)"); System.out.println("后缀计算器(sufix)"); System.out.println("前缀计算器(prefix)"); System.err.println("(注：中缀计算器不支持 ')' '(' 符号)"); System.out.print("请输入计算器类型："); Character keyword = SCANNER.next().charAt(0); switch (keyword) { case 's': SufixCalculator suffixCalculator = new SufixCalculator(Util.stringExpression(sufixExpressionList)); System.out.println("计算结果：" + suffixCalculator.calculationExpression()); break; case 'p': PrefixCalculator prefixCalculator = new PrefixCalculator(Util.stringExpression(prefixExpressionList)); System.out.println("计算结果：" + prefixCalculator.calculationExpression()); break; case 'i': if(Util.stringExpression(infixExpressionList).contains(")") || Util.stringExpression(infixExpressionList).contains("(")) { System.err.println("计算中缀表达式的计算机不支持符号：')' '('"); break; } InfixCalculator infixCalculator = new InfixCalculator(Util.stringExpression(infixExpressionList)); System.out.println("计算结果：" + infixCalculator.calculationExpression()); break; default: break; } System.out.println();System.out.println(); } }}
        
       
      
     
    
   

测试

中缀表达式转前缀和后缀表达式的测试

后缀表达式计算器的测试

前缀表达式计算器的测试

中缀表达式计算器的测试

需要注意：这里的中缀表达式不支持)和(，如下

致读者的话

这篇博文从编码、几万字笔记、做图等，花费了本人近2天的时间，期待您的三连，如果您觉得对您有帮助或者有什么问题，欢迎留言，我将对此感到非常荣幸！

最后祝每位正在拼搏的追梦人都能成功，加油！

转载地址：https://blog.csdn.net/m0_49039508/article/details/117161857 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！