表达式求值问题的记录

假设我们得到这样的一个字符串"1766-50*21+3777+21-188+2500/50"，然后根据运算规则得到它的值，怎样实现？

解：

public class ExpEvaluation {

    private static OperandStack operandStack;
    private static OperetorStack operetorStack;
    private static boolean lastCharIsNum;

    public static void main(String[] args) {
        operandStack = new OperandStack();
        operetorStack = new OperetorStack();

        lastCharIsNum = false;

        String str = "1766-50*21+3777+21-188+2500/50";
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (isOp(chars[i])){
                judgeLevel(chars[i]);
            }else {
                if (lastCharIsNum){
                    int top = operandStack.pop();
                    show("数字出栈  " + top);
                    int value = Integer.valueOf(chars[i]+"") + top*10;
                    operandStack.push(value);
                    show("数字入栈  " + value);

                }else {
                    int value = Integer.valueOf(chars[i]+"");
                    operandStack.push(value);
                    show("数字入栈  " + value);
                }
                lastCharIsNum = true;
            }
        }

        judgeLevel('#');
        System.out.println("result = " + operandStack.getTop());
        int sum = 1766-50*21+3777+21-188+2500/50;
        System.out.println("result = " + sum);
    }

    private static void show(String mes){
        boolean isShow = false;
        if (isShow) {
            System.out.println(mes);
        }

    }

    private static void judgeLevel(char aChar) {
        int level = getOpLevel(aChar);
        int lastLevel = getOpLevel(operetorStack.getTop());
        if (lastLevel >= level){
            int value1 = operandStack.pop();
            show("数字出栈  " + value1);
            int value2 = operandStack.pop();
            show("数字出栈  " + value2);
            char c = operetorStack.pop();
            show("操作符出栈  " + c);
            show(value2 + "" + c + "" + value1);
            int sum = runcal(c,value1,value2);
            operandStack.push(sum);
            show("数字入栈  " + sum);
            show("end Op and next judge");
            judgeLevel(aChar);
        }else {
            operetorStack.push(aChar);
            show("操作符入栈  " + aChar);
            lastCharIsNum = false;
        }
    }

    private static int runcal(char aChar, int value1, int value2) {
        int sum = 0;
        switch (aChar){
            case '+':
                sum = value2 + value1;
                break;
            case '-':
                sum = value2 - value1;
                break;
            case '*':
                sum = value2*value1;
                break;
            case '/':
                sum = value2/value1;
                break;
        }
        return sum;
    }

    public static boolean isOp(char c){
        if (c >= '0' &&  c<='9'){
            return false;
        }else {
            return true;
        }
    }

    public static int getOpLevel(char op) {
        int level = 0;
        switch (op) {
            case '+':
            case '-':
                level = 1;
                break;
            case '*':
            case '/':
                level = 2;
                break;
            case ' ':
                level = -1;
                break;
            case '#':
                level = 0;
                break;
        }
        return level;
    }

    static class OperetorStack {
        class OperetorNode {
            public char op;
            public OperetorNode next;

            public OperetorNode(char op, OperetorNode next) {
                this.op = op;
                this.next = next;
            }
        }

        OperetorNode top = null;
        int length = 0;

        //入栈操作
        public void push(char value){
            if (top == null){
                top = new OperetorNode(' ',null);
            }
            OperetorNode node = new OperetorNode(value,null);
            node.next = top;
            top = node;
            length++;
        }

        //出栈操作
        public char pop(){
           if (length == 0){
               show("操作符栈为空");
                   return ' ';
           }
            char value = top.op;
            top = top.next;
            length--;
            return value;
        }

        //得到栈顶元素
        public char getTop(){
            if (length <= 0){
                show("操作符栈为空");
                return ' ';
            }
            return top.op;
        }

        //判断栈是否为空
        public boolean isEmpty(){
            return length == 0;
        }
    }

    static class OperandStack {
        class OperandNode {
            public int num;
            public OperandNode next;

            public OperandNode(int num, OperandNode next) {
                this.num = num;
                this.next = next;
            }
        }

        OperandNode top = null;
        int length = 0;

        //入栈操作
        public void push(int value){
            if (top == null){
                top = new OperandNode(-1,null);
            }
            OperandNode node = new OperandNode(value,null);
            node.next = top;
            top = node;
            length++;
        }

        //出栈操作
        public int pop(){
            if (length == 0){
                show("数字栈为空");
                return -1;
            }
            int value = top.num;
            top = top.next;
            length--;
            return value;
        }

        //得到栈顶元素
        public int getTop(){
            if (length <= 0){
                show("数字栈为空");
                return -1;
            }
            return top.num;
        }

        //判断栈是否为空
        public boolean isEmpty(){
            return length == 0;
        }
    }

}