逆波兰表达式

逆波兰表达式,第1张

波兰表达式 逆波兰表达式实现计算器(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());
    }


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

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/4656098.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-11-06
下一篇 2022-11-06

发表评论

登录后才能评论

评论列表(0条)

保存