程序员笔记逆波兰表达式计算_ApeSpring的博客

//纯数组模拟栈实现(推荐)

class Solution {
    
    public static int evalRPN(String[] tokens) {
        int[] numStack = new int[tokens.length / 2 + 1];
        int index = 0;
        for (String s : tokens) {
            switch (s) {
            case "+":
                numStack[index - 2] += numStack[--index];
                break;
            case "-":
                numStack[index - 2] -= numStack[--index];
                break;
            case "*":
                numStack[index - 2] *= numStack[--index];
                break;
            case "/":
                numStack[index - 2] /= numStack[--index];
                break;
            default:
                // numStack[index++] = Integer.valueOf(s);
                //valueOf改为parseInt，减少自动拆箱装箱操作
                numStack[index++] = Integer.parseInt(s);
                break;
            }
        }
        return numStack[0];
    }
}
栈实现：
class Solution {
    // 栈实现   8 ms    36.7 MB    
    public static int evalRPN(String[] tokens) {
        Stack<Integer> numStack = new Stack<>();
        Integer op1, op2;
        for (String s : tokens) {
            switch (s) {
            case "+":
                op2 = numStack.pop();
                op1 = numStack.pop();
                numStack.push(op1 + op2);
                break;
            case "-":
                op2 = numStack.pop();
                op1 = numStack.pop();
                numStack.push(op1 - op2);
                break;
            case "*":
                op2 = numStack.pop();
                op1 = numStack.pop();
                numStack.push(op1 * op2);
                break;
            case "/":
                op2 = numStack.pop();
                op1 = numStack.pop();
                numStack.push(op1 / op2);
                break;
            default:
                numStack.push(Integer.valueOf(s));
                break;
            }

1120逆波兰中缀转后缀表达式

public static void trans(String s, StringBuilder postexp) {
        SequenceStack mystack = new SequenceStack(50);
        char temp;
        for(int i=0; i<s.toCharArray().length; ) {
            switch(s.charAt(i))
            {
            case '(':    //判定为左括号
                mystack.push('(');
                i++;
                break;
            case ')':
                temp = (char) mystack.pop();
                while(temp != '(') {
                    postexp.append(temp);
                    temp = (char) mystack.pop();
                }
                i++;
                break;
            case '+':
            case '-':
                while(!mystack.isEmpty()) {
                    temp = (char) mystack.getTop();
                    if(temp != '(') {
                        postexp.append(temp);
                        temp = (char) mystack.pop();
                    }else {
                        break;
                    }    
                }
                mystack.push(s.charAt(i));
                i++;
                break;
            case '*':
            case '/':
                while(!mystack.isEmpty()) {
                    temp = (char) mystack.getTop();
                    if(temp=='*' || temp == '/') {
                        postexp.append(temp);
                        temp = (char) mystack.pop();
                    }else {
                        break;
                    }
                }
                mystack.push(s.charAt(i));
                i++;
                break;
                
                default:
                    while(s.charAt(i)>='0' && s.charAt(i)<='9') {
                        postexp.append(s.charAt(i));
                        i++;
                    }
                    postexp.append('#');
                    break;
            }
        }
        
        while(!mystack.isEmpty()) {
            temp = (char) mystack.pop();
            postexp.append(temp);
        }
    }

计算

public static double compvalue(StringBuilder postexp) {
        double a,b,c,d,e = 0;
        
        SequenceStack mystack = new SequenceStack(50);//操作数栈
        for(int i=0; i<postexp.length(); i++) {
            switch (postexp.charAt(i))
            {
            case '+':                //判定为'+'号
                a = (double) mystack.pop();        //出栈元素a
                b = (double) mystack.pop();        //出栈元素b
                c=b+a;                //计算c
                mystack.push(c);        //将计算结果c进栈
                break;
            case '-':                //判定为'-'号
                a = (double) mystack.pop();        //出栈元素a
                b = (double) mystack.pop();        //出栈元素b
                c=b-a;                //计算c
                mystack.push(c);        //将计算结果c进栈
                break;
            case '*':                //判定为'*'号
                a = (double) mystack.pop();        //出栈元素a
                b = (double) mystack.pop();        //出栈元素b
                c=b*a;                //计算c
                mystack.push(c);        //将计算结果c进栈
                break;
            case '/':                //判定为'/'号
                a = (double) mystack.pop();        //出栈元素a
                b = (double) mystack.pop();        //出栈元素b
                if (a!=0)
                {
                    c=b/a;            //计算c
                    mystack.push(c);    //将计算结果c进栈
                    break;
                }
                else
                {    
                    System.out.println("\n\t除零错误!\n");
                    System.exit(0);        //异常退出
                }
                break;
            default:                //处理数字字符
                d=0;                //将连续的数字字符转换成对应的数值存放到d中
                while (postexp.charAt(i)>='0' && postexp.charAt(i)<='9')   //判定为数字字符
                {    
                    d=10*d+postexp.charAt(i)-'0';  //将char转成数值型的。
                    i++;
                }
                mystack.push(d);        //将数值d进栈

                break;
            }
        }
        e = (double) mystack.getTop();
        return e;
    }