如何让计算机计算算数表达式

1、前言

如果计算一个表达式：5 * (2 + 8 / 4) + 6，作为人类我们能很快利用符号的优先级进行计算。但是对于计算机来说，它并不能很好的识别这个算式，我们要把它转换成计算机可以方便识别的模式。针对于 5 * (2 + 8 / 4) + 6，它叫做中缀表达式。而计算机容易识别的表达式叫后缀表达式：5284/+*6+。然后就很方便的计算后缀表达式了。

2、转换与计算算法

转换主要靠栈，转换的算法流程：
1）从左到右进行遍历
2）遇到操作数直接输出（即收集起来）
3）遇到左括号直接入栈，括号是最高优先级。但是一旦入栈，需要把它的优先级将到最低，确保其他符号能正确入栈。
4）遇到右括号，说明括号已经结束。不断出栈，直到遇到左括号（左括号不输出）
5）遇到其它运算符，则比较该运算符与栈顶运算符的优先级，如果优先级大于栈顶优先级则直接入栈；否则出栈到小于等于该运算符
6）如果对象处理完毕,则按顺序弹出并输出栈中所有运算符

那么针对于上述表达式：5 * (2 + 8 / 4) + 6，代码如下：

public class Translate {

    public String translate(String original){
        if(original == null || original.length() == 0){
            return null;
        }
        Stack<Character> stack = new Stack<>();
        StringBuilder builder = new StringBuilder();
        Map<Character, Integer> map = new HashMap<>();
        map.put('(', 1);
        map.put('+', 2);
        map.put('-', 2);
        map.put('*', 3);
        map.put('/', 3);

        for (char ch : original.toCharArray()) {
            if(ch >= '0' && ch <= '9'){
                builder.append(ch);
            }else if(ch == '('){
                stack.push(ch);
            }else if(ch == '+' || ch == '-' || ch == '*' || ch == '/'){
                while(!stack.isEmpty() && map.get(ch) <= map.get(stack.peek())){
                    builder.append(stack.pop());
                }
                stack.push(ch);
            }else if(ch == ')'){
                while(stack.peek() != '('){
                    builder.append(stack.pop());
                }
                stack.pop();
            }
        }
        while (!stack.isEmpty()){
            builder.append(stack.pop());
        }
        return builder.toString();
    }

    public static void main(String[] args) {
        System.out.println(new Translate().translate("5*(2+8/4)+6"));
    }
}

计算算法就比较简单了：
1）遍历后缀表达式，如果遇到数字，则直接入栈；如果遇到字符则计算，并将结果入栈，一直到遍历结束。

那么对于已经变成后缀表达式的：5284/+*6+，计算代码如下：

public class Translate {

    public int calculate(String original){
        Stack<Integer> stack = new Stack<>();
        for(char ch : original.toCharArray()){
            if(ch == '+' || ch == '-' || ch == '*' || ch == '/'){
                int num1 = stack.pop(), num2 = stack.pop();
                if(ch == '+'){
                    stack.push(num2 + num1);
                }
                if(ch == '-'){
                    stack.push(num2 - num1);
                }
                if(ch == '*'){
                    stack.push(num2 * num1);
                }
                if(ch == '/'){
                    stack.push(num2 / num1);
                }
            }else{
                stack.push(ch - '0');
            }
        }

        return stack.pop();
    }

    public static void main(String[] args) {
        System.out.println(new Translate().calculate("5*(2+8/4)+6"));
    }
}

3、后记

当然，这个表达式还未考虑各种异常情况，或者数是负数的情况，或者数不是个位的情况，如果有兴趣可以参加 leetcode 的 224 题。