中缀转后缀

​ 思路分析：

1）初始化两个栈：运算符栈s1和中间结果栈s2

2）从左到右扫描中缀表达式

3）遇到操作数将其压入s2

4）遇到操作符时，将其与s1栈顶运算符比较优先级

​ 4.1）如果s1为空，或者栈顶元素为“（”直接将其压入运算符栈

​ 4.2）如果优先级比s1栈顶元素的优先级高，将其直接入栈

​ 4.3）如果优先级小于等于s1栈顶元素优先级，则将s1栈顶元素弹出并压入s2中，再次转到4.1与s1中新的栈顶元素比较

5）遇到括号

​ 5.1）如果是左括号“（“，直接压入s1

​ 5.2）如果是右括号”）“，则依次弹出s1栈顶元素，并压入s2，直到遇到”（“，并将这一对括号废弃

6）重复2~5步骤，直到表达式最右边

7）最后将其s1剩余运算符依次加入s2

8）依次弹出s2中元素输出结果就为后缀表达式

代码实现：

package com.cwnu.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/*
 * 中缀转后缀的算法实现
 * */
public class InfixtoSuffix {
    public static void main(String[] args) {
        //声明字符转
        String express = "1 + ( ( 2 + 3 ) * 4 ) - 5";
        //字符串转数组
        String[] expressArray = toStringArray(express);
        //初始化两个栈符号栈s1和中间栈s2
        Stack<String> s1 = new Stack<>();
        Stack<String> s2 = new Stack<>();
        s2 = suffixesToSuffixes(s1, s2, expressArray);
        String[] print = new String[s2.size()];
        for (int i = 0; i < s2.size(); i++) {
            print[i] = s2.get(i);
        }
        System.out.print("表达式为：");
        for (String e : print) {
            System.out.print(e + " ");
        }
    }

    //将字符串转化为数组
    public static String[] toStringArray(String string) {
        return string.split(" ");
    }

    //运算优先级
    public static int priority(String oper) {
        if (oper.equals("*") || oper.equals("/")) {
            return 1;
        } else if (oper.equals("+") || oper.equals("-")) {
            return 0;
        } else {
            return -1;
        }
    }

    //判断是否为运算符
    public static boolean isOperator(String oper) {
        return oper.equals("*") || oper.equals("/") || oper.equals("+") || oper.equals("-");
    }

    //判断是否为括号
    public static boolean isParentheses(String oper) {
        return oper.equals("(") || oper.equals(")");
    }

    //中缀转后缀
    public static Stack suffixesToSuffixes(Stack<String> s1, Stack<String> s2, String[] strings) {
        //对表达时进行扫描
        for (String itme : strings) {
            if (!isOperator(itme) && !isParentheses(itme)) {//表示为既不是运算符也不是括号，数字直接入s2
                s2.push(itme);
            } else if (isOperator(itme)) {//遇到运算符
                // 如果s1为空，或者栈顶元素为“（”直接将其压入运算符栈
                if (s1.isEmpty() || s1.peek().equals("(")) {
                    s1.push(itme);
                } else if (priority(itme) > priority(s1.peek())) {//如果优先级比s1栈顶元素的优先级高，将其直接入栈
                    s1.push(itme);
                } else if (priority(itme) <= priority(s1.peek())) {//如果优先级小于等于s1栈顶元素优先级，则将s1栈顶元素弹出并压入s2中，再次转到4.1与s1中新的栈顶元素比较
                    while (true) {
                        s2.push(s1.pop());
                        if (s1.isEmpty() || s1.peek().equals("(") || priority(itme) > priority(s1.peek())) {
                            s1.push(itme);
                            break;
                        }
                    }
                }
            } else if (isParentheses(itme)) {
                // 5.1）如果是左括号“（“，直接压入s1
                if (itme.equals("(")) {
                    s1.push(itme);
                }
                //5.2）如果是右括号”）“，则依次弹出s1栈顶元素，并压入s2，直到遇到”（“，并将这一对括号废弃
                if (itme.equals(")")) {
                    while (true) {
                        s2.push(s1.pop());
                        if (s1.peek().equals("(")) {
                            s1.pop();
                            break;
                        }
                    }
                }
            }
        }
        while (true) {
            s2.push(s1.pop());
            if (s1.isEmpty()) {
                break;
            }
        }
        return s2;
    }
}