题解 | #公式字符串求值#

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        String str = "";
        while (in.hasNext()) { // 注意 while 处理多个 case
            str += in.next();          
        }
         System.out.println(calculate(str));
    }

    public static int calculate(String str) {
        return process(str, 0)[0];
    }

    //返回值参数：第一个是从i到末端的计算值，第二个是i到达的位置
    private static int[] process(String str, int i) {
        char[] chars = str.toCharArray();
        //使用队列结构在最后求+-操作的时候直接底部出栈方便计算
        LinkedList<String> queue = new LinkedList<String>();
        //数值叠加
        int pre = 0;
        //内部括号表达式返回值
        int[] innerRes = null;
        while (i < chars.length && chars[i] != ')') {
            if (chars[i] >= '0' && chars[i] <= '9') {
                //不断累加
                pre = pre * 10 + chars[i++] - '0';
            } else if (chars[i] != '(') {
                //如果栈为空，直接把数字放进去，否则需要比较符号优先级
                addNum(queue, pre);
                queue.add(String.valueOf(chars[i++]));
                //重置pre
                pre = 0;
            } else {
                //为括号的情况
                innerRes = process(str, i + 1);
                pre = innerRes[0];
                i = innerRes[1] + 1;
            }
        }
        //把最后的数字加入表达式
        addNum(queue, pre);
        //最后表达式全为+-操作，从头部出队进行依次加减
        pre = Integer.valueOf(queue.pollFirst());
        while (!queue.isEmpty()) {
            if (queue.pollFirst().equals("+")) {
                pre = pre + Integer.valueOf(queue.pollFirst());
            } else {
                pre = pre - Integer.valueOf(queue.pollFirst());
            }
        }
        //返回)的位置或者表达式末端
        return new int[] {pre, i};
    }

    private static void addNum(LinkedList<String> queue, int pre) {
        if (!queue.isEmpty()) {
            String stackTop = queue.peekLast();
            if (stackTop.equals("*") || stackTop.equals("/")) {
                stackTop = queue.pollLast();
                int temp = Integer.valueOf(queue.pollLast());
                pre = stackTop.equals("*") ? temp * pre : temp / pre;
            }
        }
        queue.add(String.valueOf(pre));
    }
}