送外卖小公司OA

中缀表达式转后缀表达式的方法：

• 遇到操作数：直接输出(添加到后缀表达式中)
• 栈为空时，遇到运算符，直接入栈
• 遇到左括号：将其入栈
• 遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出。
• 遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈
• 最终将栈中的元素依次出栈，输出。

输入是用space分割的expression，数字可以是negative number，不用处理括号

public class EvalExpression {
    public static void main(String[] args) {
        String exp = "6 / 3 / 2";
        int res = eval(exp);
        System.out.println(res);
    }
    static int eval(String exp) {
        String[] tokens = exp.split(" ");
        Stack<Integer> nums = new Stack<Integer>();
        Stack<String> operators = new Stack<String>();
        
        Set<String> operand = new HashSet<String>();
        operand.add("+");
        operand.add("-");
        operand.add("*");
        operand.add("/");
        
        for (String token : tokens) {
            if (operand.contains(token)) {
                if (operators.isEmpty()) {
                    operators.push(token);
                }
                else {
                    if (token.equals("+") || token.equals("-")) {
                        while (! operators.isEmpty()) {
                            String tmp = operators.pop();
                            int num2 = nums.pop(), num1 = nums.pop();
                            nums.push(operate(num1, num2, tmp));
                        }                        
                    }
                    if (token.equals("*") || token.equals("/")) {
                        while (! operators.isEmpty() && (operators.peek().equals("*") || operators.peek().equals("/"))) {
                            String tmp = operators.pop();
                            int num2 = nums.pop(), num1 = nums.pop();
                            nums.push(operate(num1, num2, tmp));
                        } 
                    }
                    operators.push(token);
                }
            }
            else {
                nums.push(Integer.parseInt(token));
            }
        }
        while (! operators.isEmpty()) {
            String tmp = operators.pop();            
            int num2 = nums.pop(), num1 = nums.pop();
            nums.push(operate(num1, num2, tmp));
        }
        return nums.pop();
    }
}