栈的应用-四则运算（中缀与后缀表达式转换--Java源码）

本文主要是介绍栈的应用-四则运算（中缀与后缀表达式转换--Java源码），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

参考链接
结合原文章，做了一定修改，增加Java源码实现

- 1. 概述
- 2. 后缀表达式计算
- 3. 中缀表达式转后缀表达式
- 4. 源代码实现

1. 概述

对于四则运算表达式的计算，是输入数据结构中栈的应用，即重点是中缀表达式转换为后缀表达式

2. 后缀表达式计算

为了解释后缀表达式的好处，我们先来看看，计算机是如何计算后缀表达式的
后缀表达式实例9 3 1 - 3 * + 10 2 / +
计算规则：从左到右遍历表达式的每个数字和符号，遇到数字就进栈，遇到是符号，就将处于栈顶的两个数字出栈，进行计算，然后计算结果进栈，一直到最终获得结果。
计算过程：

3. 中缀表达式转后缀表达式

我们把平时标准的四则运算表达式比如9+(3-1)*3+10/2叫做中缀表达式。
中缀表达式：9+(3-1)*3+10/2转换后缀表达式9 3 1 - 3 * + 10 2 / +

转换规则：
1. 当当前字符为数字时，直接输出；
2. 当当前字符为(时，将其压栈；
3. 当当前字符为)时，则弹出堆栈中最上的(之前的所有运算符并输出，然后删除堆栈中的(；
4. 当当前字符为运算符时，则依次弹出堆栈中优先级大于等于当前运算符的(到”(“之前为止)，输出，再将当前运算符压栈；
  最后弹出所有栈中的内容输出
转换过程

4. 源代码实现

package data_structure;import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;/*** 栈的应用* https://blog.csdn.net/u011857433/article/details/79993385* 四则运算表达式求职，中缀表达式与后缀表达式转换*/
public class ReversePoland {public static void main(String[] args) {//        Calculation1("9 3 1 - 3 * + 10 2 / +");System.out.println(Calculation2("9 + ( 3 - 1 ) * 3 + 10 / 2"));}/*** 计算后缀表达式* @param inputString 9 3 1 - 3 * + 10 2 / + 以空格分隔*/public static int Calculation1(String inputString){String[] input = inputString.split(" ");Stack<Integer> stack = new Stack<>();for (int i = 0; i < input.length; i++) {String s = input[i];if (isNumber(s))  //如果是数字，则入栈stack.push(Integer.valueOf(s));else {//遇到运算符，则从栈中弹出两个数字，进行运算int n1 = stack.pop();int n2 = stack.pop();int res = 0;switch (s){case "+":res = n1 + n2;break;case "-":res = n2 - n1;break;case "*":res = n1 * n2;break;case "/":res = n2 / n1;break;}stack.push(res);}}return stack.pop();}/*** 将中缀表达式转化为后缀表达式* @param string 9 + ( 3 - 1 ) * 3 + 10 / 2* @return*/public static String Calculation2(String string){Stack<String> stack = new Stack();String[] chars = string.split(" ");String res = "";for (int i = 0; i < chars.length; i++) {String s = String.valueOf(chars[i]);if (isNumber(s)){if (res.length()==0)res += s;elseres += " "+s;}else {if (s.equals("(")){stack.push(s);}else {if (s.equals(")")){String t = "";String s1 = "";while (!(t = stack.pop()).equals("(")){s1 += " "+t;}res += s1;}else {int priority = getPriority(s);String s1 = "";boolean flag = false;while (!stack.empty()){flag = false;s1 = stack.pop();if (s1.equals("(")){
//                                stack.push("(");break;}if (getPriority(s1) >= priority){res += " " + s1;flag = true;}}if (!s1.equals("") && !flag)stack.push(s1);stack.push(s);}}}}while (!stack.empty()){res += " " + stack.pop();}return res;}//获取运算符的优先级public static int getPriority(String s){Map<String,Integer> map = new HashMap<>();map.put("+",0);map.put("-",0);map.put("*",1);map.put("/",1);map.put("(",2);map.put(")",2);return map.get(s);}public static boolean isNumber(String c){Pattern pattern = Pattern.compile("^(0|[1-9][0-9]*)$");Matcher matcher = pattern.matcher(c);boolean res = matcher.find();return res;}
}