中缀表达式转后缀表达式

根据中缀表达式求逆波兰表达式（思路清晰）

具体步骤

1. 初始化两个栈，一个临时栈tempStack，一个操作符栈operaStack
2. 从左至右扫描中缀表达式
3. 遇到操作数直接入tempStack
4. 遇到操作符时（不包括括号）
   4.1 若operaStack为空或者栈顶为’(’，则直接入operaStack
   4.2 若operaStack不为空且栈顶元素不为’(’，比较栈顶操作符和当前操作符优先级，若比栈顶优先级高，直接压入operaStack（乘除优先级大于加减）
   4.3 否则取出operaStack栈顶操作符并压入tempStack栈，接着回到4.1步骤与新的栈顶元素进行比较
5. 遇到括号时
   5.1 如果是左括号’(’，压入operaStack
   5.2 如果是右括号’)’，则依次弹出operaStack操作符并压入tempStack，直到遇到左括号为止。丢弃左右括号
6. 重复2到5步骤，直到表达式最右边
7. 将operaStack剩余的元素依次弹出并压入tempStack
8. 依次弹出tempStack，逆序之后为后缀表达式，即逆波兰表达式

代码实现

package com.twilight.algorithm.calculator;

import java.util.Stack;

public class ExpressConvert {

    public static void main(String[] args) {
        System.out.println(infixToSuffix("1+((2+3)*4)-5")); // 123+4*+5-
    }

    public static String infixToSuffix(String s) {
        // 1. 初始化两个栈，一个临时栈tempStack，一个操作符栈operaStack
        Stack<Character> operaStack = new Stack<>();
        Stack<Character> tempStack = new Stack<>();
        // 2. 从左至右扫描中缀表达式
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int cLevel = CharLevel.level(c);
            // 3. 遇到操作数直接入tempStack
            if(cLevel == 0) {
                tempStack.push(c);
            } else if(cLevel == 4) {
                // 5. 遇到括号时
                // 5.1 如果是左括号'('，压入operaStack
                operaStack.push(c);
            } else if(cLevel == 1) {
                // 5.2 如果是右括号')'
                while(true) {
                    // 5.2 则依次弹出operaStack操作符并压入tempStack，直到遇到左括号位置。丢弃左右括号
                    char cc = operaStack.pop();
                    if(CharLevel.level(cc) == 4) {
                        break;
                    }
                    tempStack.push(cc);
                }
            } else {
                // 4. 遇到操作符时（不包括括号）
                while(true) {
                    // 4.1 若operaStack为空或者栈顶为'('，则直接入operaStack
                    if(operaStack.isEmpty() || operaStack.peek() == '(') {
                        operaStack.push(c);
                        break;
                    }
                    char cc = operaStack.peek();
                    int ccLevel = CharLevel.level(cc);
                    // 4.2 比较栈顶操作符和当前操作符优先级，若比栈顶优先级高，直接入operaStack
                    if(cLevel > ccLevel) {
                        operaStack.push(c);
                        break;
                    } else {
                        // 4.3 否则取出operaStack栈顶操作符并压入tempStack栈，接着回到4.1步骤
                        tempStack.push(operaStack.pop());
                    }
                }
            }
            // 6. 重复2到5步骤，直到表达式最右边
        }
        while(!operaStack.isEmpty()) {
            // 7. 将operaStack剩余的元素依次弹出并压入tempStack
            tempStack.push(operaStack.pop());
        }
        StringBuilder sb = new StringBuilder();
        // 8. 依次弹出tempStack，逆序之后即为逆波兰表达式，即后缀表达式
        while(!tempStack.isEmpty()) {
            sb.append(tempStack.pop());
        }
        return sb.reverse().toString();
    }
}

字符等级判断类
这个判断思路来源
https://blog.csdn.net/KeThink/article/details/88071518?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-4.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-4.nonecase

package com.twilight.algorithm.calculator;

public class CharLevel {

    public static int level(char c) {
        if("(".indexOf(c) > -1) {
            return 4;
        } else if("*/".indexOf(c) > -1) {
            return 3;
        } else if("+-".indexOf(c) > -1) {
            return 2;
        } else if(")".indexOf(c) > -1) {
            return 1;
        } else {
            // 数字
            return 0;
        }
    }

}

本文地址：https://blog.csdn.net/XlxfyzsFdblj/article/details/107487089