（四）栈—中缀表达式转后缀表达式

 一、基本介绍

二、应用实例

        将中缀表达式"1+((2+3)x4)-5" 转换为 后缀表达式"1 2 3 + 4 x + 5 -"
        思路：
            1.初始化两个栈：运算符栈s1和存储中间结果的栈s2；
            2.从左至右扫描中缀表达式；
            3.扫描到操作数直接压入栈s2中；
            4.扫描到运算符时，比较其与s1栈顶运算符的优先级：
                    4.1若s1为空或者栈顶运算符为左括号，则直接将扫描到的运算符压入s1；
                    4.2否则，若扫描到的运算符优先级比s1栈顶运算符高，也将其压入栈s1；
                    4.3否则，将s1栈顶运算符弹出并压入到栈s2中，同时再次与s1中新的栈顶运算符比较；
            5.扫描到括号时：
                    5.1若扫描到的是左括号，则直接压入到栈s1中；
                    5.2若扫描到的是右括号，则依次弹出s1栈顶运算符，并压入栈s2，直至遇到左括号为止，最后将栈s1中的左括号丢弃；
            6.重复步骤2-5，直到扫描到中缀表达式的最右边；
            7.将s1中剩余的运算符依次弹出并压入栈s2；
            8.依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式。
 

package stack;import java.util.ArrayList;
import java.util.Collections;
import java.util.List;public class InffixToSuffixExpression {public static void main(String[] args) {String inffixExpression = "1+((2+3)*4)-5";List<String> inffiExpression_list = toList(inffixExpression); // 获得中缀表达式对应的List集合List<String> suffixExpression_list = toParseSuffixExpression(inffiExpression_list);Collections.reverse(suffixExpression_list); // 将list集合逆序，即为对应的后缀表达式String suffixExpression = String.join("", suffixExpression_list); // 将list集合转为字符串System.out.println("中缀表达式：" + inffixExpression);System.out.println("后缀表达式：" + suffixExpression);System.out.println("后缀表达式(逆波兰表达式)求值：" + calculate(suffixExpression_list));}//  inffixExpression = "1+((2+3)*4)-5";public static List<String> toList(String inffixExpression) {List<String> list = new ArrayList<>();char ch = ' ';int index = 0;String temp;while (index != inffixExpression.length()) {//  如果该字符是非数字，则将其直接放入list数组if ((ch = inffixExpression.charAt(index)) < 48 || (ch = inffixExpression.charAt(index)) > 57) {list.add(ch + "");index++;} else {//  如果该字符是数字，则需要考虑多位数的情况temp = "";  // 每循环一轮，都需将字符串置为空while (index < inffixExpression.length() && (((ch = inffixExpression.charAt(index)) >= 48) && ((ch = inffixExpression.charAt(index)) <= 57))) {temp += ch;index++;}list.add(temp);}}return list;}private static List<String> toParseSuffixExpression(List<String> list) {Stack operStack = new Stack(32);Stack tempStack = new Stack(32);String op = "";//  2、从左至右扫描中缀表达式for (String item : list) {//  3、遇到是数字时if (item.matches("\\\\d+")) {  // 匹配多位数tempStack.push(item);//  3.1、遇到左括号} else if (item.equals("(")) {operStack.push(item);//  3.2、遇到右括号} else if (item.equals(")")) {while (!operStack.peek().equals("(")) {tempStack.push(operStack.pop());}operStack.pop(); // 将左括号出栈//  4、遇到运算符时} else {// 4.1、operStack栈为空 或 栈顶元素为（ 时，直接将元素入栈if (operStack.isEmpty() || operStack.peek().equals("(")) {operStack.push(item);// 4.2、该字符元素优先级比栈顶元素优先级高，则直接入栈} else if (operStack.priority(item) > operStack.priority(operStack.peek())) {operStack.push(item);} else {//  4.3、该字符元素的优先级 <= 栈顶元素的优先级while(!operStack.isEmpty() && operStack.priority(item) <= operStack.priority(operStack.peek())) {tempStack.push(operStack.pop());}//  退出while循环时，一般为当前元素的优先级高于栈顶元素的优先级，所以要将该元素直接入栈operStack.push(item);}}}//  5、将operStack剩余的运算符弹出并压入tempStackwhile (!operStack.isEmpty()) {tempStack.push(operStack.pop());}//  6、弹出tempStack的元素放入List数组中返回，结果的逆序即为对应的后缀表达式List<String> resultList = new ArrayList();while(!tempStack.isEmpty()) {resultList.add(tempStack.pop());}return resultList;}private static String calculate(List<String> list) {Stack stack = new Stack(16);int num1 = 0;int num2 = 0;int res = 0;for (String item : list) {if (item.matches("\\\\d+")) { // 匹配多位数字stack.push(item);} else {num1 = Integer.parseInt(stack.pop());num2 = Integer.parseInt(stack.pop());if (item.equals("+")) {res = num1 + num2;} else if (item.equals("-")) {res = num2 - num1;} else if (item.equals("*")) {res = num1 * num2;} else if (item.equals("/")) {res = num2 / num1;} else {System.out.println("无效运算符！");}stack.push(res+"");}}//  栈中最后的值即为表达式的结果return stack.pop();}}class Stack {private String[] arr;private int maxSize;private int top;public Stack(int maxSize) {this.maxSize = maxSize;this.arr = new String[maxSize];this.top = -1;}public String peek() {return arr[top];}public void push(String val) {if (isFull()) {throw new RuntimeException("栈满，入栈失败！");}arr[++top] = val;}public String pop() {if (isEmpty()) {throw new RuntimeException("栈空，出栈失败！");}return arr[top--];}public void print() {if (isEmpty()) {throw new RuntimeException("栈空，出栈失败！");}System.out.print("栈元素：");for (int i = top; i >= 0 ; i--) {System.out.print(arr[i] + " ");}System.out.println();}public boolean isEmpty() {if (top == -1) {return true;}return false;}public boolean isFull() {if (top == maxSize - 1) {return true;}return false;}public int priority(String ch) {if (ch == "x" || ch == "/") {return 1;} else if (ch == "+" || ch == "-") {return 0;} else {return -1;}}
}