基于栈的后缀算术表达式求值

本篇文章主要是记录数据结构习题解析与实验指导（李冬梅）的课后实验三。

这次实验是利用后缀表达式来进行算术表达式求值，上篇博文介绍的是利用中缀表达式来进行算术表达式的求值。而这次实验是利用中缀表达式转换为后缀表达式，然后再利用后缀表达式进行求值。（之所以要转换为后缀表达式，是因为使用后缀表达式进行求值非常简单）

1 基本思想

首先说一下后缀表达式，后缀表达式又称为逆波兰表达式，后缀指的就是运算符在操作数的后面。计算方法简而言之就是遇到数字就进栈，遇到操作符就运算。
然后再说一下如何将中缀表达式转换为后缀表达式。从左到右遍历字符串，如果是数字就输出，如果是操作符，就判断与栈顶符号的优先级，是右括号或优先级不高于栈顶符号的则栈顶符号依次输出，并将当前符号进栈，若是优先级高于栈顶符号则进栈。 优先级可以参考下面的代码。

2 代码实现

import java.util.Stack;

class Expression2 {
    private Stack<Character> stack;
    private Stack<Integer> stack2;
    private char[] data;

    public Expression2(String s) {
        stack = 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 = stack2.pop();
            t = -t;
            stack2.push(t);
            break;
        case '+':
            t1 = stack2.pop();
            t2 = stack2.pop();
            stack2.push(t1 + t2);
            break;
        case '-':
            t1 = stack2.pop();
            t2 = stack2.pop();
            stack2.push(t2 - t1);
            break;
        case '*':
            t1 = stack2.pop();
            t2 = stack2.pop();
            stack2.push(t1 * t2);
            break;
        case '/':
            t1 = stack2.pop();
            t2 = stack2.pop();
            stack2.push(t2 / t1);
            break;
        }
    }

    public int calcuate(char[] t) {
        for(char c : t) {
            if(c >= '0' && c <= '9') {
                stack2.push(c - 48);
            } else {
                calculate2(c);
            }
        }
        return stack2.pop();
    }

    public char[] translate() {
        char[] temp = new char[data.length];
        int j = 0;
        for (int i = 0; i < data.length; ++i) {
            if (data[i] >= '0' && data[i] <= '9') {
                temp[j++] = data[i];
            } else {
                if (stack.empty()) {
                    stack.push(data[i]);
                } else {
                    if (data[i] == ')') {
                        char t = stack.pop();
                        while (t != '(') {
                            temp[j++] = t;
                            t = stack.pop();
                        }
                    } else if (data[i] == '(') {
                        stack.push(data[i]);
                    } else {
                        int p1 = getPriority(data[i]);
                        int p2 = getPriority(stack.peek());
                        while (p2 >= p1) {
                            temp[j++] = stack.pop();
                            if (stack.empty()) {
                                break;
                            }
                            p2 = getPriority(stack.peek());
                        }
                        stack.push(data[i]);
                    }
                }
            }
            if (i == data.length - 1) {
                while (!stack.empty()) {
                    temp[j++] = stack.pop();
                }
            }
        }
        return temp;
    }
}

public class Test12 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String test = "9+(3-1)*3+6/2";
        Expression2 e = new Expression2(test);
        char[] t = e.translate();
        System.out.println(e.calcuate(t));
    }

}

注意： 两篇关于表达式的博文都只能对10以内的数进行计算，如果想要对大于10的数进行计算，需要进行一定的判断，然后进行入栈操作。