java实现表达式求值

[例子和习题出自数据结构(严蔚敏版), 本人使用Java进行实现.  转载请注明作者和出处,  如有谬误, 欢迎在评论中指正. ]

对整数表达式求值. 表达式中可能包含+-*/四则运算, 以及括号, 比如:4 + 2 * 3 - 10 / 5, (1+2) * (4 + 5) - (9 / 7)等.

思路: 将括号之间的内容当做子表达式求值, 得出子表达式的结果后就可以去掉括号了.

使用optr栈存储运算符, opnd栈存储操作数. 解析表达式, 如果得到操作数就存入opnd栈中, 如果得到运算符, 就根据所得的运算符和optr栈顶运算符的优先级比较结果, 进行相应的操作.

 

1. 定义优先级和优先级表

/**
 * 运算符优先权
 */
public enum Precede {
    /**
     * 优先权高
     */
    LARGER,
    /**
     * 优先权低
     */
    LESS;

    /**
     * 优先级表
     *      +   -   *   /
     *  +   >    >    <    <
     *  -   >    >    <    <
     *  *   >    >    >    >
     *  /   >    >    >    >
     */
    private static Precede[][] precedes = new Precede[4][4];

    static {
        // 根据优先级表初始化precedes数组
        for (int i = 0; i < precedes.length; i++) {
            for (int j = 0; j < precedes[i].length; j++) {
                if ((i == 0 || i == 1) && j > 1) {
                    precedes[i][j] = LESS;
                } else {
                    precedes[i][j] = LARGER;
                }
            }
        }
    }

    /**
     * 判断2个运算符的优先级
     */
    public static Precede judgePrecede(char operand1, char operand2) {
        int left = getIndex(operand1);
        int right = getIndex(operand2);
        return precedes[left][right];
    }

    /**
     * 获取运算符对应的数组索引
     */
    private static int getIndex(char operand) {
        switch (operand) {
        case '+':
            return 0;
        case '-':
            return 1;
        case '*':
            return 2;
        case '/':
            return 3;
        default:
            throw new IllegalArgumentException();
        }
    }
}

 

2. 表达式求值

/**
 * 整数表达式运算
 */
public class EvaluateExpression {
    /**
     * 表达式
     */
    private String expression;
    /**
     * 最初的表达式
     */
    private String initExpression;
    /**
     * 运算符栈
     */
    private MyStack<Character> optr = new MyArrayStack<Character>();
    /**
     * 操作数栈
     */
    private MyStack<Integer> opnd = new MyArrayStack<Integer>();
    /**
     * 表明下一个是否应该是数字
     */
    private boolean numberNext;

    public EvaluateExpression(String expression) {
        this.expression = expression;
        this.initExpression = expression;
        numberNext = true;
    }

    /**
     * 求值
     */
    public Integer evaluate() {
        delBlank();
        handleParentheses();

        while (true) {
            if ("".equals(expression)) {
                break;
            }

            if (expression.matches("^-?\\d+.*$") && numberNext) {
                opnd.push(getInteger());
                continue;
            } else {
                Character operand = expression.charAt(0);
                numberNext = true;
                expression = expression.substring(1);
                Character pop;                  if(optr.isEmpty()){                  pop=null;                 }else{                  pop = optr.pop();                 }

                if (pop == null) {
                    optr.push(operand);
                    continue;
                } else {
                    Precede precede = Precede.judgePrecede(pop, operand);
                    switch (precede) {
                    // 优先级高时运算前2个操作数
                    case LARGER: {
                        optr.push(operand);
                        Integer next = opnd.pop();
                        Integer last = opnd.pop();
                        evaluateNow(last, pop, next);
                        break;
                    }
                    // 优先级低时运算前一个操作数和后一个操作数
                    case LESS: {
                        optr.push(pop);
                        Integer last = opnd.pop();
                        Integer next = getInteger();
                        evaluateNow(last, operand, next);
                        break;
                    }
                    }
                }
            }
        }

        // 运算结果
        Integer result = null;
        if (optr.length() == 0 && opnd.length() == 1) {
            result = opnd.pop();
        } else if (optr.length() == 1 && opnd.length() == 2) {
            Integer next = opnd.pop();
            Integer last = opnd.pop();
            evaluateNow(last, optr.pop(), next);
            result = opnd.pop();
        } else {
            throw new RuntimeException();
        }
        return result;
    }

    /**
     * 进行实际的运算，并将结果入栈
     */
    private void evaluateNow(Integer last, Character operand, Integer next) {
        switch (operand) {
        case '+':
            opnd.push(last + next);
            break;
        case '-':
            opnd.push(last - next);
            break;
        case '*':
            opnd.push(last * next);
            break;
        case '/':
            opnd.push(last / next);
            break;
        }
    }

    /**
     * 获得表达式开头部分的整数
     */
    private Integer getInteger() {
        StringBuilder sb = new StringBuilder();
        int count = 0; // 整数位
        boolean lessZero = false; // 是否是负数

        if (expression.startsWith("-")) {
            sb.append("-");
            count++;
            lessZero = true;
        }

        int i = (lessZero ? 1 : 0);
        for (; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (c >= '0' && c <= '9') {
                sb.append(c);
                count++;
            } else {
                break;
            }
        }
        expression = expression.substring(count);
        numberNext = false;
        return Integer.valueOf(sb.toString());
    }

    /**
     * 处理括号. 将括号内的字符串作为子表达式计算.
     */
    private void handleParentheses() {
        while (expression.contains("(")) {
            // 左括号的索引
            int left = 0;
            // 右括号的索引
            int right = 0;
            // 左括号的数量
            int count = 0;

            // 求出左括号索引
            left = expression.indexOf('(');

            // 求出对应的右括号索引
            for (int i = left; i < expression.length(); i++) {
                char c = expression.charAt(i);
                if (c == ')') {
                    count--;
                    // count为0时才是对应的右括号
                    if (count == 0) {
                        right = i;
                        break;
                    }
                } else if (c == '(') {
                    count++;
                } else {
                    continue;
                }
            }
            // 左右括号之间是一个子表达式, 计算子表达式的值，并根据结果构造出新的表达式
            EvaluateExpression evaluateExpression = new EvaluateExpression(expression.substring(left + 1, right));
            expression = expression.substring(0, left) + evaluateExpression.evaluate()
                    + expression.substring(right + 1);
        }
    }

    /**
     * 删除表达式中的空白字符
     */
    private void delBlank() {
        expression = expression.replaceAll("\\s", "");
    }

    @Override
    public String toString() {
        return initExpression;
    }
}

 

3. 进行测试

 

@Test
public void testEvaluate() {
    EvaluateExpression expression = new EvaluateExpression("1 + 2 ");
    System.out.println(expression + " = " + expression.evaluate());

    expression = new EvaluateExpression("4 + 2 * 3 - 10 / 5");
    System.out.println(expression + " = " + expression.evaluate());

    expression = new EvaluateExpression("(1+2) * (4 + 5) - (9 / 7)");
    System.out.println(expression + " = " + expression.evaluate());

    expression = new EvaluateExpression("(1 + (3 * (4 - 9)))");
    System.out.println(expression + " = " + expression.evaluate());

    expression = new EvaluateExpression("(1 + (3 * (4 - 9))) + (3 * (2 + 3))");
    System.out.println(expression + " = " + expression.evaluate());
}

测试的结果为:

1 + 2  = 3

4 + 2 * 3 - 10 / 5 = 8

(1+2) * (4 + 5) - (9 / 7) = 26

(1 + (3 * (4 - 9))) = -14

(1 + (3 * (4 - 9))) + (3 * (2 + 3)) = 1

 

可见结果是正确的.