中缀表达式与后缀表达式

### 中缀表达式与后缀表达式的区别

中缀表达式是一种常见的算术表示法，在这种形式下，操作符位于两个操作数之间。例如 `A + B` 是一个典型的中缀表达式[^1]。

相比之下，后缀表达式（也称为逆波兰表示法 RPN），所有的操作符都放在其对应的参数之后。同样的加法运算会写作 `AB+` 。这种方式消除了括号的需求并简化了计算过程。

### 转换方法

为了实现从中缀到后缀的转换，通常采用栈这一数据结构来辅助处理。具体来说：

- 初始化一个新的空栈用于保存暂时无法输出的操作符；
- 遍历输入字符串中的每一个字符：
- 如果遇到的是数字，则直接将其加入输出队列；
- 若为左括号'('则压入栈顶；
- 当碰到右括号')'时，持续弹出栈内元素直到遇见匹配的左括号为止，并丢弃这对括号；
- 对于其他任何操作符，当且仅当前置优先级不低于即将进入栈的新操作符时才允许执行弹出动作；随后将新读取到的操作符推入栈中。

最后一步是从栈底至栈顶依次取出剩余未处理完毕的操作符并将它们追加到最终的结果序列里去。

public class InfixToPostfix {
    private static final Map<Character, Integer> precedence = new HashMap<>();

    static {
        precedence.put('+', 1);
        precedence.put('-', 1);
        precedence.put('*', 2);
        precedence.put('/', 2);
    }

    public static String infixToPostfix(String expression) {
        StringBuilder result = new StringBuilder();
        Deque<Character> stack = new ArrayDeque<>();
        
        for (char c : expression.toCharArray()) {
            switch(c){
                case '+':
                case '-':
                case '*':
                case '/': 
                    while (!stack.isEmpty() && precedence.get(stack.peek()) >= precedence.get(c)) {
                        result.append(stack.pop());
                    }
                    stack.push(c);
                    break;
                    
                case '(':
                    stack.push(c);
                    break;

                case ')':
                    Character tmp;
                    while ((tmp=stack.pop()) != '(') {
                        result.append(tmp);
                    }
                    break;
                
                default:// operand
                    result.append(c);
            }
        }
    
        while(!stack.isEmpty()){
            result.append(stack.pop());
        }
        
        return result.toString();
    }
}