栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

栈的应用:Java语言(中缀表达式转后缀表达式并计算结果)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

栈的应用:Java语言(中缀表达式转后缀表达式并计算结果)

中缀表达式对于我们人来说,是很好理解的,比如: 8 + ( ( 4 + 5 )× 2);
但对于计算机来说,可就不太那么容易了,相较于中缀表达式,后缀表达式更适合计算机来进行运算,那么我们该如何将一个中缀表达式转换成后缀表达式进而进行运算呢?
首先我们来解决中缀表达式转后缀表达式的问题:
为了能够更加简洁清楚的讲清楚这件事,我画一个图来描述这个过程。

中缀表达式转后缀表达式

看图大家还是有点蒙,毕竟逻辑还是比较多的,我们来看一个例子,或许会好很多。
就拿: (1+2)*5/4-9 来举例子。


关键来了:





代码实现:

package com.qiqi.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PolandNotation {
    public static void main(String[] args) {

        //将中缀表达式转换成后缀表达式的一个功能实现
        //(1+2)*5/4-9;为了方便遍历,将该字符串放入对应的List中
        //将得到的中缀表达式对应的List ---> 后缀表达式对应的List

        String expressionall = "( 1+ 2)* 5 /4 - 9 ";
        String expression = replaceAllBlank(expressionall);
        
        List ls_middle = toInfixExpressionList(expression);
        System.out.println("中缀表达式对应的list:" +ls_middle);

        List ls_latter = paraSuffixExpression(ls_middle);

        System.out.println("后缀表达式对应的list:" + ls_latter);

        System.out.printf("表达式=%d",calculate(ls_latter));
    }


    //去除所有的空白字符
    public static String replaceAllBlank(String s ){
        // \s+ 匹配任何空白字符,包括空格、制表符、换页符等等,
        return s.replaceAll("\s+","");
    }


    //方法: paraSuffixExpression(List ls)
    //将得到的中缀表达式对应的List ---> 后缀表达式对应的List
    public static List paraSuffixExpression(List ls){
        //初始化栈
        Stack s1 = new Stack(); //符号栈
        //s2整个过程中,并没有出栈操作,并且最后还需要逆序输出,所以转换成列表使用。
        //Stack s2 = new Stack<>(); //存储中间结果的栈
        List s2 = new ArrayList();

        //遍历ls
        for(String item : ls){
            if(item.matches("^[-|+]?([1-9]\d*|0)[\.\d+]?$")){ //利用正则表达式匹配整数和小数
                //如果是数字,加入s2
                s2.add(item);
            }else if(item.equals("(")){
                //如果是左括号,入s1
                s1.push(item);
            }else if(item.equals(")")){
                //如果是右括号,则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时这一对括号(已经运算顺序改变,作业完成)将丢弃
                while(!s1.peek().equals("(")){
                    s2.add(s1.pop());
                }
                //将 "(" 弹出s1栈,消除小括号
                s1.pop();
            }else{
                //当item的优先级小于等于栈顶运算符("()"不算)
                while(s1.size() != 0 && Operation.getValue(s1.peek()) >=  Operation.getValue(item) ){
                    s2.add(s1.pop());
                }
                //将item压入栈中
                s1.push(item);
            }
        }
        //将s1中的运算符加入到s2中
        while(s1.size() != 0){
            s2.add(s1.pop());
        }
        return s2;//存放到了List中,正常按顺序输出即可。
    }






    //方法:toInfixExpressionList(String  s)
    //将中缀表达式转成对于的List
    public static List toInfixExpressionList(String  s){
        List ls = new ArrayList();
        int i = 0; //遍历字符串
        String str;//对多位数进行拼接
        char c; //每遍历到一个字符,就放入c中
        do{
            //如果是一个非数字,就需要加入到ls
            if((c = s.charAt(i)) < 48 ||(c = s.charAt(i)) >57){
                ls.add("" + c);
                i++;
            }else{
                //如果是一个数
                str = "";
                //0 :48 ;  9 :57
                while (i < s.length() && ((c = s.charAt(i)) >= 48) && ((c = s.charAt(i)) <= 57)) {
                    str += c;
                    i++;
                }
                ls.add(str);
            }
        }while(i < s.length());
        return ls;
    }

    //方法:calculate(List ls)
    //遍历栈,计算结果(传进来的是后缀表达式)
    public static int calculate(List ls){
        //创建一个栈
        Stack stack = new Stack<>();
        //遍历
        for(String item : ls){
        
            if(item.matches("\d+")){ //正则表达式,匹配的是多位数
               stack.push(item);
            }else{
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;   //用来存放算出来的结果
                if(item.equals("+")){
                    res = num1 + num2;
                }else if(item.equals("-")){
                    res = num1 - num2;
                }else if(item.equals("*")){
                    res = num1 * num2;
                }else if(item.equals("/")){
                    res = num1 / num2;
                }else{
                    throw new RuntimeException("运算符有误!");
                }
                //res入栈
                stack.push(String.valueOf(res));
            }
        }
        //最后留在栈中的数据就是结果
        return Integer.parseInt(stack.pop());
    }
}



//编写一个类,功能:可以返回运算符对应的优先级
class Operation{
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;

    //
    public static int getValue(String operation){
        int result = 0;
        switch(operation){
            case "+":
                result += ADD;
                break;
            case "-":
                result += SUB;
                break;
            case "*":
                result += MUL;
                break;
            case "/":
                result += DIV;
                break;
            case "(":
                break;
            case ")":
                break;
            default:
//              throw new RuntimeException("输入的运算符有误!");
                System.out.println("输入的运算符不匹配");
                break;
        }
        return result;
    }

}


这里的程序没有考虑小数的问题,如果遇到小数,还需要做一些逻辑上的处理,这里就不多介绍了。
昨天家里的天空也很漂亮

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/972492.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号