中缀算术表达式求值

这是记录数据结构习题解析与实验指导（李冬梅）实验二的一篇博文，具体内容就是给个中缀算术表达式，然后进行求值。
中缀算术表达式的求值方式有很多种，我学的有两种，一种就是用两个栈进行求解，也就是本文中所讲的，一种就是先转换为后缀表达式，然后后缀表达式通过一个栈进行求解，这是下一篇博文所要讲的。我所知道的还有一种方法，是利用树来进行算术表达式的求解。因为还没学，所以暂时先不写相应的博文。

1 基本思想

两个栈，一个存数字，一个存操作符。当要入栈的操作符的优先级高于操作符栈的优先级是，入栈，否则，弹出操作符进行计算，直至栈顶操作符的优先级低于当前操作符，然后将当前操作符压栈。如果遇到左括号，直接入栈，遇到右括号，则一直将操作符退栈，直到碰到左括号为止。+和-的优先级相同*和/优先级相同。
这里还有一个负号的问题需要鉴别，如果前面为‘）’或者数字时，才可能是减号，其余情况均是负号

2 代码

import java.util.Stack;

public class Test11 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String test = "(3*5+3)/6+3+-3*3";
        ExpressionCalculate e = new ExpressionCalculate(test);
        e.proceed();
    }

}

class ExpressionCalculate {
    private Stack stack1;
    private Stack stack2;
    private char[] data;

    public ExpressionCalculate(String s) {
        stack1 = new Stack();
        stack2 = new Stack();
        data = s.toCharArray();
    }

    public int getPriority(char c) {
        int priority = 0;
        if (c == '#') {
            priority = 3;
        } else if (c == '*' || c == '/') {
            priority = 2;
        } else if (c == '+' || c == '-') {
            priority = 1;
        } else if (c == '(') {
            priority = 0;
        }
        return priority;
    }

    public void calculate2(char c) {
        int t1, t2;
        switch (c) {
        case '#':
            int t = (int) stack1.pop();
            t = -t;
            stack1.push(t);
            break;
        case '+':
            t1 = (int) stack1.pop();
            t2 = (int) stack1.pop();
            stack1.push(t1 + t2);
            break;
        case '-':
            t1 = (int) stack1.pop();
            t2 = (int) stack1.pop();
            stack1.push(t2 - t1);
            break;
        case '*':
            t1 = (int) stack1.pop();
            t2 = (int) stack1.pop();
            stack1.push(t1 * t2);
            break;
        case '/':
            t1 = (int) stack1.pop();
            t2 = (int) stack1.pop();
            stack1.push(t2 / t1);
            break;
        }
    }

    public void calculate(char c) {
        char t;
        if (c == ')') {
            t = (char) stack2.pop();
            while (t != '(') {
                calculate2(t);
                t = (char) stack2.pop();
            }
        } else {
            t = (char) stack2.pop();
            int p1 = getPriority(c);
            int p2 = getPriority(t);
            while (p2 >= p1) {
                calculate2(t);
                if (stack2.empty()) {
                    break;
                }
                t = (char) stack2.pop();
                p2 = getPriority(t);
            }
            if (p2 < p1) {
                stack2.push(t);
            }
            stack2.push(c);
        }
    }

    public void proceed() {
        for (int i = 0; i < data.length; ++i) {
            if (data[i] >= '0' && data[i] <= '9') {
                stack1.push(new Integer(data[i]) - 48);
            } else if (data[i] == '(') {
                stack2.push(data[i]);
            } else if (data[i] == '-') {
                if (i != 0 && (data[i - 1] == ')' || data[i-1] >= '0' && data[i-1] <= '9')) {
                    int p1 = getPriority(data[i]);
                    int p2 = getPriority((char) stack2.peek());
                    if (p1 > p2) {
                        stack2.push(data[i]);
                    } else {
                        calculate(data[i]);
                    }
                } else {
                    stack2.push('#'); //#用来表示负号
                }
            } else if (data[i] == ')') {
                calculate(data[i]);
            } else {
                if (stack2.empty()) {
                    stack2.push(data[i]);
                } else {
                    int p1 = getPriority(data[i]);
                    int p2 = getPriority((char) stack2.peek());
                    if (p1 > p2) {
                        stack2.push(data[i]);
                    } else {
                        calculate(data[i]);
                    }
                }
            }
            if (i == data.length - 1) {
                if (stack2.empty()) {
                    System.out.println(stack1.pop());
                } else {
                    while (!stack2.empty()) {
                        char c = (char) stack2.pop();
                        calculate2(c);
                    }
                    System.out.println(stack1.pop());
                }
            }
        }
    }

}

代码写的有些差😌，功能应该可以实现的。如果有不对的地方，可以在下方评论，我会及时进行修改的。