逆波兰表达式

逆波兰表达式 逆波兰表达式实现计算器（Java）

1. 什么是逆波兰表达式？
          在我们生活中常常用到中缀表达式进行数学上的表达，因为中缀表达比较符合人类的思维方式，便于人类去理解和学习，但计算机却不能理解中缀表达式，因为它只会服从您对它输入的指令，所以可以用什么方式让计算机去理解我们的数学表达式呢？于是就用到了我们现在所说的逆波兰表达式。
          那么什么是逆波兰表达式呢？逆波兰表达式又称后缀表达式，列如现在给定一个中缀表达式 :
   a + b*c
   它的逆波兰表达式形式就是:
   a b c * +
2. 中缀表达式转逆波兰表达式实现思路
       我们以 (a+b*c)*d  这个例子来讲述实现思路；
       1.第一步：
       创建两个栈s1与s2（s1存符号、s2存数字）
   
       2.第二步：
       对 (a+b*c)*d  这个表达式从左至右依次扫描，判断s1是否为空或者扫描到的字符是否为“（”，如果s1为空或者扫描到的字符为“（”，则将扫描到的符号入s1栈，例:
   

    3.第三步：
移动扫描指针，让它指向下一个字符，例：

执行第二步，发现此时s1不为空且a不为“（”，因为a为数字，于是将其入s2数字栈，例：

    4.第四步：
移动扫描指针，让它指向下一个字符：

执行第二步，s1不为空且“+”不为“（”，但由于“+”为运算符，于是与s1栈顶的符号比较优先级，但由于s1当前栈顶的符号为“（”，所不予比较直接入s1符号栈，下次遇到该情况也这样处理。
    5.第5步：
继续扫描下一个字符，例：

执行第二步，s1不为空且b为数字，所以将b入s2数字栈。

    6.第6步：
继续扫描下一个字符，例：

执行第二步，s1不为空且“*”不为“（”，但由于“*”为运算符，所以让它与s1栈顶的运算符比较优先级，当前s1栈顶的运算符为“+”，“*”的优先级大于“+”，于是将“*”压入s1符号栈。例：

    7.第7步：
继续扫描下一个字符，例：

执行第二步，s1不为空且c不为“（”，但c为数字所以将其入s2数字栈。例：

    8.第8步：
继续扫描下一个字符，例：

执行第二步，s1不为空且“）”不为“（”，“）”为右括号，当我们遇到右括号时，我们将s1栈中的运算符一次d出到s2中，直至遇到左括号“（”停止且需将“（”也d出，但不d入s2。例：

    9.第9步：
继续扫描下一个字符，例：

执行第二步，s1为空且“*”不为数字所以将“*”压入s1。例：

    10.第10步：
继续扫描下一个字符，例：

执行第二步，s1不为空且“d”不为“（”，但b是数字所以压入s2，又因为d为表达式最后一个字符所以将s1中的运算符全部d入s2。例：

    11.第11步：
    现在将s2中所有数字或符号依次d出：*d+*cba 然后进行反向就得到了我们需要的逆波兰表达式：abc*+d*。

现在逆波兰表达式得到了，就需对它进行计算

对逆波兰表达式进行计算比较简单
假设a=5、b=7、c=3、d=6；
将以上数字代入abc*+d*
首先我们创建一个栈s

然后从左至右扫描5 7 3 * + 6 *，为数字则压入栈s中

573

当扫描到运算符时，我们将栈顶的数字d出来两个进行运算然后再将结果压入栈s中，例如现在扫描到了*号：

5

3*7=21

521

继续扫描，现在扫描到+号，如果扫描到数字则将数字压入栈s中

5+21=26

26

继续扫描，现在扫描到d，为数字所有将d压入栈s

266

继续扫描，现在扫描到*，我们将栈顶的数字d出来两个进行运算然后再将结果压入栈s中
26*6=156

156

最后取出156，156即为最后的结果。
通过验证（5+7*3）*6=156；

java代码实现

 
    //将字符串表达式转换为List表
    public static List changeExpressForList(String express) {
        int index = 0;//指针
        String str = "";
        List expressForList = new ArrayList();
        do {
            if (index < express.length() && express.charAt(index) < 47 || express.charAt(index) > 58) {
                expressForList.add(express.charAt(index)+"");
                index++;
            } else {
                while (index < express.length() && express.charAt(index) >= 47 && express.charAt(index) <= 58) {
                    str = str + express.charAt(index);
                    index++;
                }
                expressForList.add(str);
                str = "";
            }
        } while (index < express.length());
        return expressForList;
    }

    //返回符号优先级，用于比对运算符的优先级
    public static int compare(String sign) throws RuntimeException{
        final int PLUS = 1;
        final int SUB = 1;
        final int MUL = 2;
        final int DIV = 2;

        switch (sign) {
            case "+":
                return PLUS;
            case "-":
                return SUB;
            case "*":
                return MUL;
            case "/":
                return DIV;
            case "(":
                return 0;
            default:
                throw new RuntimeException("运算符错误！");
        }

    }

    
 //中缀表达式转后缀表达式方法
    public static List changeSuffix(List express) throws Exception {
        Stack s1 = new Stack();
        List s2 = new ArrayList();
        for (String str:express) {
            if (str.matches("\d+")) {
                s2.add(str);
            } else if (s1.isEmpty() || str.equals("(")) {
                s1.push(str);
            } else if (str.equals(")")) {
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop();
            } else {
                if (compare(s1.peek()) > compare(str)) {
                    s2.add(s1.pop());
                }
                s1.push(str);
            }
        }
        if (!s1.empty()) {
            s2.add(s1.pop());
        }
        return s2;
    }

//对字符串列表进行扫描并进行计算
    public static int counter(List strings) throws Exception {
        //创建栈
        Stack stack = new Stack<>();
        for (String str : strings) {
            if (str.matches("\d+")) {
                stack.push(str);
            } else {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int result;
                switch(str) {
                    case "+":
                        result = num1 + num2;
                        break;
                    case "-":
                        result = num2 - num1;
                        break;
                    case "*":
                        result = num1 * num2;
                        break;
                    case "/":
                        result = num2/num1;
                        break;
                    default:
                        throw new Exception("运算错误");
                }
                stack.push(result+"");
            }
        }
        return Integer.parseInt(stack.pop());
    }

新人，有写的不好的地方还请谅解，请多多指教