用逆波兰表达式解决四则运算 - 高飞网
74 人阅读

用逆波兰表达式解决四则运算

2016-12-22 11:10:34

    逆波兰表达式,是利用数据结构“栈”,巧妙的解决复杂的四则运算问题的。本文用java来实现加减乘除运算,关于逆波兰表达式的原理说明,请参考:四则运算表达式求值

运算符的判断逻辑

/**
 * 运算的元素,包括操作符、括号、运行数
 * 
 * @data Dec 22, 2016 10:55:33 AM
 */
enum E {
    ADD(1), SUB(1), MUL(2), DIV(2), LEFT_BRACKET(0), RIGHT_BRACKET(0), NUM(0);
    private int p;

    E(int p) {
        this.p = p;
    }

    public static E getEnum(String e) {
        Pattern p = Pattern.compile("\\d+");
        if (e.equals("+")) {
            return ADD;
        } else if (e.equals("-")) {
            return SUB;
        } else if (e.equals("*")) {
            return MUL;
        } else if (e.equals("/")) {
            return DIV;
        } else if (e.equals("(")) {
            return LEFT_BRACKET;
        } else if (e.equals(")")) {
            return RIGHT_BRACKET;
        } else if (p.matcher(e).matches()) {
            return NUM;
        }
        return null;
    }

    /**
     * 是否为数字
     * 
     * @param s
     * @return
     */
    public static boolean isNum(String s) {
        E e = getEnum(s);
        if (e == null) {
            return false;
        }
        return e == NUM;
    }

    /**
     * 优先级比较
     * 
     * @param e
     * @return
     */
    public int p(E e) {
        if (this == NUM || this == LEFT_BRACKET || this == RIGHT_BRACKET//
                || e == NUM || e == LEFT_BRACKET || e == RIGHT_BRACKET//
                || this == e) {
            return 0;
        }
        return this.p - e.p;
    }
}

运算器的具体实现

/**
 * 用栈实现四则运算
 * 
 * @author xuyanhua
 * @data Dec 22, 2016 12:26:02 AM
 */
public class Calc {
    private String exp;// 表达式

    public Calc(String exp) {
        this.exp = exp;
    }

    /**
     * 转为逆波兰中缀表达式
     * 
     * @return
     */
    private List<String> rpn() {
        List<String> result = new ArrayList<String>();
        Stack<String> tmp = new Stack<String>();
        String[] es = exp.split(" ");
        for (String e : es) {
            boolean isNum = E.isNum(e);
            if (isNum) {// 遇到数字就输出到结构中
                result.add(e);
            } else {// 遇到符号
                E e2 = E.getEnum(e);
                if (e2 == E.RIGHT_BRACKET) {// 如果是右括号,将栈中左括号前的都输出到结果
                    while (!tmp.isEmpty()) {
                        String t = tmp.pop();
                        if (E.getEnum(t) == E.LEFT_BRACKET) {
                            break;
                        }
                        result.add(t);
                    }
                } else if (!tmp.isEmpty() && e2.p(E.getEnum(tmp.peek())) < 0) {// 运算符的优先级小于栈顶符号,出栈并输出到结果中
                    while (!tmp.isEmpty()) {
                        String t = tmp.pop();
                        result.add(t);
                    }
                }
                if (e2 != E.RIGHT_BRACKET) {// 不是右括号,则都进栈
                    tmp.push(e);
                }
            }
        }
        while (!tmp.isEmpty()) {// 将栈中剩余的都出栈输出到结果中
            String t = tmp.pop();
            result.add(t);
        }
        return result;
    }

    /**
     * 总计算方法
     * 
     * @return
     */
    public int calc() {
        List<String> rpn = rpn();
        Stack<String> tmp = new Stack<String>();
        Iterator<String> iterator = rpn.iterator();
        while (iterator.hasNext()) {
            String s = iterator.next();
            if (E.isNum(s)) {// 数字就入栈
                tmp.push(s);
            } else {// 如果是符号,就提取栈中的两个操作数运算
                Integer n2 = Integer.parseInt(tmp.pop());
                Integer n1 = Integer.parseInt(tmp.pop());
                int res = calc(n1, n2, s);
                tmp.push(res + "");// 运算结果再进栈
            }
        }
        return Integer.parseInt(tmp.pop());
    }

    /**
     * 计算加减乘除法
     * 
     * @param n1
     * @param n2
     * @param op
     * @return
     */
    private int calc(int n1, int n2, String op) {
        E e = E.getEnum(op);
        switch (e) {
        case ADD:
            return n1 + n2;
        case SUB:
            return n1 - n2;
        case MUL:
            return n1 * n2;
        case DIV:
            return n1 / n2;
        default:
            break;
        }
        return 0;
    }

    public static void main(String[] args) {
        String exp = "9 + ( 3 - 1 ) * 3 + 10 / 2";
        System.out.println(exp + " = " + new Calc(exp).calc());
        String exp2 = "2 + ( 10 / 2 ) + 3 * 2";
        System.out.println(exp2 + " = " + new Calc(exp2).calc());
    }
}

计算过程:


计算结果:

9 + ( 3 - 1 ) * 3 + 10 / 2 = 20
2 + ( 10 / 2 ) + 3 * 2 = 13

还没有评论!
54.197.104.221