中缀表达式转后缀表达式

将中缀表达式转为后缀表达式，输入 a+bc/d-a+f/b 输出 abcd/+a-fb/+
要求：语言不限；输入输出均为单个字符串；操作数用单个小写字母表示，操作符只需支持 +-*/，按照四则运算顺序确定优先级，不包含括号

输入描述:
一个字符串为合法的中缀表达式
字符串长度不超过200000

输出描述:
对应的后缀表达式

输入例子1:
a+b*c/d-a+f/b

输出例子1:
abc*d/+a-fb/+

考察点： 栈，模拟
易错点：
日常生活中接触的一般为中缀表达式，后缀表达式被称为逆波兰式，是将运算符写在操作数之后的一种形式。简单来说就是如果存在E1 op E2形式的表达式，op是任意二元操作符，则E的后缀式为E1'E2' op，E1'和E2'分别为E1和E2的后缀式。

解法：栈
观察样例，可以发现操作数的相对顺序并没有变化，只是操作符顺序的变化；实际只需把操作符利用栈缓存，再结合优先级比较进行输出即可。思路如下：用一个栈来维护中缀表达式中的操作符，首先，遍历中缀表达式中的每个字符，如果是字母就直接输出，作为后缀表达式的一部分；如果是操作符，则比较其和栈顶元素的优先级，如果优先级小于等于栈顶元素，则将栈中元素依次出栈，直到栈为空，或者栈中元素的优先级小于当前元素；然后把该元素压栈。最后遍历完字符串之后把栈中元素全部出栈即可。

import java.util.*;
public class Main {
    public static void main(String[] argc) {
        Scanner scaner = new Scanner(System.in);
        char[] midStr = scaner.next().toCharArray();
        HashMap<Character, Integer> map = new HashMap();
        map.put('+', 1); map.put('-', 1); map.put('*', 2); map.put('/', 2);

        Stack<Character> s = new Stack();
        for(int i=0; i<midStr.length; i++) {
            if(midStr[i] >= 'a' && midStr[i] <= 'z') {
                System.out.print(midStr[i]);
            } else {
                //针对优先级相等的情况（是否先输出不影响运算结果）；不过根据输入输出实例可以看出，
                //是数字在前的先运算，所以这里=的情况也先打印出来
                while(!s.isEmpty() && map.get(midStr[i])<=map.get(s.peek())) {
                    System.out.print(s.pop());
                }
                s.push(midStr[i]);
            }
        }
        while(!s.isEmpty()) {//最后别忘了把栈内剩余的出栈
            System.out.print(s.pop());
        }
    }
}