中缀表达式转逆波兰表达式并计算

发布于 2020-04-17  214 次阅读


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

中缀表达式:数学中的标准表达式,二叉树中序遍历,A+B*(C-D)-E/F
后缀表达式:计算机识别的表达式,二叉树的后序遍历,ABCD-*+EF/-

tree

四则运算规则

  1. 乘除优先级大于加减
  2. 括号优先级最高
  3. 同优先级从左到右依次计算

优先级表

  • isp 是 in stack priority 栈内优先数
  • icp 是 in coming priority 栈外优先数
操作符 # ( *,/ +,-
isp 0 1 5 3 6
icp 0 6 4 2 1
  1. 为什么加一个'#'号?
    这样可以不用判断栈空。
  2. 为什么同一个运算符栈内优先数大于栈外?
    为了解决同级运算符从左到右依次计算问题
  3. 为什么栈外左括号优先级最高,右括号优先级最低,栈内则相反,栈内左括号优先级等于栈外右括号?
    因为括号优先级最高,所以栈外我们把左括号设为最高,右括号设置为最低,这样保证左括号一定可以入栈,右括号一定不能入栈,用右括号只是用来匹配左括号的,为了保证匹配,栈内括号优先数与栈外相反,栈内的其他运算符优先数都大于右括号,这样可依次出栈直到左括号,保证了括号内先计算

    案例分析

    a*(b+c)#

步骤 扫描项 项类型 动作 栈内 输出
0 '#'号入栈 #
1 a 运算数 输出 # a
2 * 运算符 isp(#) < icp(*) ,入栈 #* a
3 ( 运算符 isp(*) < icp((),入栈 #*( a
4 b 运算数 输出 #*( ab
5 + 运算符 isp(() < icp(+),入栈 #*(+ ab
6 c 运算数 输出 #*(+ abc
7 ) 运算符 isp(+) < icp()),出栈,输出 #*( abc+
isp(() = icp()),出栈,不输出 #* abc+
isp(*) < icp()),出栈,输出 # abc+*
8 # 运算符 isp(#) = icp(#),出栈,结束 abc+*

总结:

  1. 运算数直接输出
  2. 栈外优先级高,入栈
  3. 栈内优先级高,循环出栈,直至低于或者相等
  4. 优先级相等,出栈,不输出。由上表,我们也不用判断是括号还是#号,#号只有末尾有,遍历到末尾就结束

代码实现

import java.util.*;
public class CalcExpression {

    public static void main(String []argv) {
        CalcExpression calc = new CalcExpression();

        System.out.println(calc.tosuffix("15*22/((22-6)*3)"));
    }

    public String tosuffix(String mix) {
        Map<Character,Integer> isp = new HashMap<>(7);
        Map<Character,Integer> icp = new HashMap<>(7);
        isp.put('#',0);isp.put('(',1);isp.put('*',5);isp.put('/',5);isp.put('+',3);isp.put('-',3);isp.put(')',6);
        icp.put('#',0);icp.put('(',6);icp.put('*',4);icp.put('/',4);icp.put('+',2);icp.put('-',2);icp.put(')',1);

        char[] mid = (mix+'#').toCharArray();

        Deque<Character> stack = new LinkedList<Character>();
        stack.offer('#');

        StringBuilder res = new StringBuilder(mix.length());
        for(int i = 0;i < mid.length;) {
            while(Character.isDigit(mid[i]) || mid[i] == '.') {
                res.append(mid[i]);
                i++;
            }
            if(i-1 >= 0 && Character.isDigit(mid[i-1]))//为了方便计算在操作符和运算数之间加上空格
                res.append(' ');
            //栈内运算符优先级大于外运算符优先级 出栈
            while(isp.get(stack.peek()) > icp.get(mid[i])) {
                res.append(stack.pop());
                res.append(' ');// 操作符之间也加上空格
            }

            // 栈内优先级低,入栈
            if(isp.get(stack.peek()) < icp.get(mid[i]))
                stack.push(mid[i]);
            else if(isp.get(stack.peek()) == icp.get(mid[i]))//优先级相等出栈
                stack.pop();

            i++;
        }
        res.deleteCharAt(res.length()-1);//删除末尾空格
        return res.toString();
    }
}
//15 22 * 22 6 - 3 * /

计算

思路

计算就很简单了,如果是操作数直接入栈,如果是运算符,则从栈中取出两个操作数计算,把结果入栈,循环往复,最后的栈顶就是结果。

public int calcSuffix(String suffix) {
        char [] copy = suffix.toCharArray();
        Deque<Integer> stack = new LinkedList<>();

        for(int i = 0;i < suffix.length();i++) {
            if(Character.isDigit(copy[i])) {
                int num = copy[i] - '0';
                while(i+1 < suffix.length() && Character.isDigit(copy[i+1])){
                    num = num * 10 + copy[++i] - '0';
                }
                stack.push(num);
            }else if(copy[i] == ' ') {
                continue;
            }else {
                int n2 = stack.pop();
                int n1 = stack.pop();

                switch(copy[i]) {
                    case '+': stack.push(n1 + n2);break;
                    case '-': stack.push(n1 - n2);break;
                    case '*': stack.push(n1 * n2);break;
                    case '/': stack.push(n1 / n2);break;
                }
            }
        }

        return stack.pop();
    }

存在问题

无法计算负数和小数


天空没有鸟的痕迹,但我已飞过。