1.图解中缀表达式转后缀表达式

通过 数据结构-01-图解后缀表达式值计算方式 我们了解到后缀表达式（例如：9 3 1 - 3 * + 10 2 /+）对计算机运算的方便，但是它却让我们这些人类十分的难受，因此我们需要在设计一个，中缀表达式转后缀表达式的程序来一劳永逸.

规则：依次遍历表达式，
1.如果是数字就添加到后缀表达式上（相反于数据结构-01-图解后缀表达式值计算方式 ）
2.如果是符号就更栈顶Top符号比较优先级，低的输入会导致出栈（就是栈中高于或者等于都会全部出栈到后缀表达式上）
（符号的优先顺序为，乘除 > 加减 > 括号（括号的情况比较特殊，请结合代码和图解详细分析））

这里是一个 中缀表达式“9+(3-1)×3+10÷2”转化为后缀表达式 "9 3 1 - 3 * + 10 2 /+"的例子（我们使用空格将元素分开)

new 一个空栈
1.第一个是数字9，1.数字就添加到后缀表达式上

 2.第二个是+，判断栈顶的，只有低的输入才会导致出栈，因此这里将+加号入栈

 3.第三个是左括号 （ ，这里比较特殊，因为是左括号直接入栈

4.第四个是数字3，.数字就添加到后缀表达式上

 5.第五个是减号， 我们需要判断栈顶的符号，左括号的优先级是最小的，这里直接将减号入栈

 6.第六个是1，.数字就添加到后缀表达式上

7.第七-个是右括号，括号是优先级最低的，特殊，我们直接找到左括号，将括号中的东西减号(-)出栈

 8.第八个是乘法，判断符号优先级高于加法，因为只有低级输入才会导致出栈，这里直接入栈

 9.第九个是 3，数字直接输出到后缀表达式中

 10.第十个是 +，低级输入会导致出栈（这里的+号的等级小于 * 等于 + ，所以栈中的 * 和 +好都会出栈，然后第十个加号入栈）

 11.第十一个是 10，数字直接全部输出到后缀表达式（大家请这里思考一个问题:像10这样的2位数或者多位数我们如何遍历得到的是一个元素 10，而不是2个元素 1,0 呢？（后面的代码将会实现这个功能））

 12.第十二个是除 / ，符号比较优先级 ，除法的优先级高于加法，只有低输入才会导致出栈，-所以这里直接入栈

 13.第十三 是 2，数字直接输出到后缀表达式中，循环结束

 14.循环结束后将栈中所有的元素依次出栈，-添加到后缀表达式后面。程序结束

2.代码

如果你不能很好的理解这个代码，建议画出
1.后缀表达式的计算方法-图解
2.图解中缀表达式转后缀表达式

java

/**
 * @author 嘉文
 */
public class InfixToPostfix {
    public String infixToPostfix(String infix) {
        //init stack
        MyStack myStack = new MyStack(infix.length());
        //postfix.
        StringBuilder postfix = new StringBuilder();
        int length = infix.length();
        for (int i = 0; i < length; i++) {
            char tempChar;
            char charAt = infix.charAt(i);
            switch (charAt) {
                //左括号直接入栈，不用过多解释
                case '(':
                    myStack.push(charAt);
                    break;
                //如果遇到 +-，低级会导致一次出栈.
                case '+':
                case '-':
                    //出栈
                    while (!myStack.isEmpty()) {
                        tempChar = myStack.pop();
                        if (tempChar == '(') {
                            myStack.push(tempChar);
                            break;
                        }
                        postfix.append(" ").append(tempChar);
                    }
                    myStack.push(charAt);
                    break;
                case '*':
                case '/':
                    while (!myStack.isEmpty()){
                        tempChar = myStack.pop();
                        if (tempChar == '('||tempChar == '+' ||tempChar == '-') {
                            myStack.push(tempChar);
                            break;
                        }
                        postfix.append(" ").append(tempChar);
                    }
                    myStack.push(charAt);
                    break;
                case ')':
                    while (!myStack.isEmpty()){
                        tempChar = myStack.pop();
                        if (tempChar != '('){
                            postfix.append(" ").append(tempChar);
                        }else {
                            break;
                        }
                    }
                    break;
                default:
                    postfix.append(" ").append(charAt);
                    //if length enough
                    if (i<length-1){
                        int j = i + 1;
                        char nextNumber = infix.charAt(j);
                        while ((nextNumber+"").matches("^[0-9]*")&&j<length){
                            postfix.append(nextNumber);
                            nextNumber = infix.charAt(++j);
                        }
                        i = j-1;
                    }
                    break;


            }
        }
        while (!myStack.isEmpty()) {
            postfix.append(" ").append(myStack.pop());
        }
        return postfix.toString().trim();
    }
    public int getValueOfInfix(String infix){
        String postfix = infixToPostfix(infix);
        String[] items = postfix.split(" ");
        MyStack myStack = new MyStack(items.length);
        int length = items.length;
        for (int i = 0; i < length; i++) {
            String tempItem = items[i];
            switch (tempItem){
                case "+":
                    char first = myStack.pop();
                    char second = myStack.pop();
                    int result = (int)second + (int)first;
                    myStack.push((char)result);
                    break;
                case "-":
                    char first2 = myStack.pop();
                    char second2 = myStack.pop();
                    int result2 = (int)second2 - (int)first2;
                    myStack.push((char)result2);
                    break;
                case "*":
                    char first3 = myStack.pop();
                    char second3 = myStack.pop();
                    int result3 = (int)second3 * (int)first3;
                    myStack.push((char)result3);
                    break;
                case "/":
                    char first4 = myStack.pop();
                    char second4 = myStack.pop();
                    int result4 = (int)second4 / (int)first4;
                    myStack.push((char)result4);
                    break;
                //if is number.
                default:
                    int charInt = Integer.parseInt(tempItem);
                    myStack.push((char)charInt);
                    break;
            }
        }
        return myStack.pop();
    }

    /**
     * 这是一个简单的栈实现
     */
    class MyStack {
        private char[] stackArray;
        private int topIndex ;

        public MyStack(int maxSize) {
            stackArray = new char[maxSize];
            topIndex = -1;
        }
        public void push(char newTopItem){
            stackArray[++topIndex] = newTopItem;
        }
        public char pop(){
            return stackArray[topIndex--];
        }
        public char peek(){
            return stackArray[topIndex];
        }
        public boolean isEmpty(){
            return topIndex<0;
        }
    }
}

　　测试

    public static void main(String[] args) {
        int valueOfInfix = new InfixToPostfix().getValueOfInfix("9+(3-1)*3+10/2");
        System.out.println(valueOfInfix);
    }

　　输出：

计算正确

转自：https://blog.csdn.net/jarvan5/article/details/109207355