前往小程序,Get更优阅读体验!
立即前往
发布
社区首页 >专栏 >【Java数据结构和算法】009-栈:前缀、中缀、后缀表达式(逆波兰表达式)

【Java数据结构和算法】009-栈:前缀、中缀、后缀表达式(逆波兰表达式)

作者头像
訾博ZiBo
发布2025-01-06 16:35:32
发布2025-01-06 16:35:32
1230
举报
文章被收录于专栏:全栈开发工程师

0、警醒自己

1、学习不用心,骗人又骗己;

2、学习不刻苦,纸上画老虎;

3、学习不惜时,终得人耻笑;

4、学习不复习,不如不学习;

5、学习不休息,毁眼伤身体;

7、狗才等着别人喂,狼都是自己寻找食物;

一、前缀表达式

1、概述

①前缀表达式(波兰表达式):前缀表达式又称波兰式,前缀表达式的运算符位于操作数之前;

②举例说明: (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6;

(PS:符号逆序走前面,数字顺序走后面;)

(PS:这么看来前缀表达式就是符号放前面,类似“1+1”就是中缀表达式,那后缀表达式就是将符号放后面(实际上不完全相似,具体见后缀表达式))

2、前缀表达式的计算求值逻辑

从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(栈顶元素 和 次顶元素),并将结果入栈;重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果;

例如:(3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 , 针对前缀表达式求值步骤如下:

①从右至左扫描,将6、5、4、3压入堆栈;

②遇到+运算符,因此弹出3和4(3为栈顶元素,4为次顶元素),计算出3+4的值,得7,再将7入栈;

③接下来是×运算符,因此弹出7和5,计算出7×5=35,将35入栈 最后是-运算符,计算出35-6的值,即29,由此得出最终结果;

二、中缀表达式

1、概述

①中缀表达式就是常见的运算表达式,如(3+4)×5-6;

②中缀表达式的求值是我们人最熟悉的,但是对计算机来说却不好操作(前面我们讲的案例就能看的这个问题),因此,在计算结果时,往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式);

三、后缀表达式

1、概述

后缀表达式又称逆波兰表达式,与前缀表达式相似,只是运算符位于操作数之后;

中举例说明: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –;

再比如:

正常的表达式

逆波兰表达式

a+b

a b +

a+(b-c)

a b c - +

a+(b-c)*d

a b c – d * +

a+d*(b-c)

a d b c - * +

a=1+3

a 1 3 + =

2、后缀表达式计算求值逻辑

从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 和 栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果;

例如:(3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:

①从左至右扫描,将3和4压入堆栈;

②遇到+运算符,因此弹出4和3(4为栈顶元素,3为次顶元素),计算出3+4的值,得7,再将7入栈;

③将5入栈;

④接下来是×运算符,因此弹出5和7,计算出7×5=35,将35入栈;

⑤将6入栈;

⑥最后是-运算符,计算出35-6的值,即29,由此得出最终结果;

PS:根据逻辑说明可以很简单地实现计算逻辑,现在的关键问题就是如何将中缀表达式转成后缀表达式了;

3、逆波兰计算器

表达式:

正常表达式:a+(b-c)*d —— 逆波兰表达式:a b c – d * +

例如:3+(8-5)*4;

要求:

①输入一个逆波兰表达式(后缀表达式),使用栈(Stack), 计算其结果;

②支持小括号和一位整数,因为这里我们主要讲的是数据结构,因此计算器进行简化,只支持对整数的计算;

代码实现:

(使用后缀表达式计算)

代码语言:javascript
复制
package com.zb.ds;

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

public class MStack {
    public static void main(String[] args) {
        //表达式3+(8-5)*4 ——> 3 8 5 – 4 * +
        String expression = "3 8 5 - 4 * +";//为了方便,我们将表达式每个单位之间使用空格隔开
        //创建一个数栈
        Stack<Integer> numStack = new Stack<>();
        //遍历表达式
        String[] split = expression.split(" ");
        List<String> list = new ArrayList<>(Arrays.asList(split));
        for (String s : list) {
            //如果不是符号,就入栈
            if(!isOperator(s)){
                //入栈之前转成数字
                int num = Integer.parseInt(s);
                numStack.push(num);
                System.out.println(num + "入栈成功!");
            }else {
                //是符号,弹出两个数,进行计算,并将计算的结果入栈
                Integer num1 = numStack.pop();
                Integer num2 = numStack.pop();
                //注意运算的顺序
                int res = cal(num1, num2, s);
                numStack.push(res);
                System.out.println(res + "入栈成功!");
            }
        }
        //最后栈里面只有一个值,就是结果
        System.out.println("最终计算结果:" + numStack.pop());
    }
    //判断是否是符号
    //判断是否是一个操作符
    public static boolean isOperator(String s){
        return s.equals("+")  || s.equals("-") || s.equals("*") || s.equals("/");
    }

    //计算方法
    public static int cal(int num1, int num2, String oper){
        int res;//res用来存储计算结果
        switch (oper){
            case "+":
                res = num1 + num2;
                break;
            case "-":
                res = num2 - num1;
                break;
            case "*":
                res = num1 * num2;
                break;
            case "/":
                res = num2 / num1;
                break;
            default:
                throw new RuntimeException("意料之外的情况,操作符为:" + oper);
        }
        return res;
    }
}
运行结果:
代码语言:javascript
复制
3入栈成功!
8入栈成功!
5入栈成功!
3入栈成功!
4入栈成功!
12入栈成功!
15入栈成功!
最终计算结果:15

四、中缀表达式转后缀表达式【重点】

1、步骤

①初始化两个栈:运算符栈s1和储存中间结果的栈s2;

②从左至右扫描中缀表达式;

③遇到操作数时,将其压s2;

④遇到运算符时,比较其与s1栈顶运算符的优先级:

如果s1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;

否则,若优先级比栈顶运算符的高,也将运算符压入s1;

否则,将s1栈顶的运算符弹出并压入到s2中,再次转到(4-1)与s1中新的栈顶运算符相比较;

⑤遇到括号时:

(1) 如果是左括号“(”,则直接压入s1;

(2) 如果是右括号“)”,则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃;

⑥重复步骤2至5,直到表达式的最右边;

⑦将s1中剩余的运算符依次弹出并压入s2;

⑧依次弹出s2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式;

2、举个例子

举例说明: 将中缀表达 式“1+((2+3)×4)-5”转 换为后缀表达式的过程如下:

(结果为 "1 2 3 + 4 × + 5 –")

扫描到的元素

s2(栈底->栈顶)

s1 (栈底->栈顶)

说明

1

1

数字,直接入栈

+

1

+

s1为空,运算符直接入栈

(

1

+ (

左括号,直接入栈

(

1

+ ( (

同上

2

1 2

+ ( (

数字

+

1 2

+ ( ( +

s1栈顶为左括号,运算符直接入栈

3

1 2 3

+ ( ( +

数字

)

1 2 3 +

+ (

右括号,弹出运算符直至遇到左括号

×

1 2 3 +

+ ( ×

s1栈顶为左括号,运算符直接入栈

4

1 2 3 + 4

+ ( ×

数字

)

1 2 3 + 4 ×

+

右括号,弹出运算符直至遇到左括号

-

1 2 3 + 4 × +

-

-与+优先级相同,因此弹出+,再压入-

5

1 2 3 + 4 × + 5

-

数字

到达最右端

1 2 3 + 4 × + 5 -

s1中剩余的运算符

3、说明

我们看到,中缀表达式转后缀表达式实现算法是相当复杂的,我们学习之后运用,很难自创一个这样的新算法;

举例子:

降龙十八掌:

学习——运用【低层次】;

自创【高层次】;

算法 = 武功秘籍:

你是跟着别人的武功秘籍走,还是自创武功,这就是层次的区别!

掌握算法两重天:

第一重:学会,然后灵活运用;

第二重:自创,然后发扬光大;

4、代码实现

(根据思路自己写出了代码)

代码语言:javascript
复制
package com.zb.ds;

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

//中缀表达式转后缀表达式
public class MeToEe {
    public static void main(String[] args) {
        //中缀表达式例子:1+((2+3)×4)-5
        String expression = "1+((2+3)×4)-5";
        //①初始化两个栈:运算符栈operatorStack和储存中间结果栈numberStack;
        //运算符栈
        Stack<Character> operatorStack = new Stack<>();
        //储存中间结果栈
        Stack<Character> resultStack = new Stack<>();
        //②从左至右扫描中缀表达式;
        char[] chars = expression.toCharArray();
        for (char c : chars) {
            //③遇到操作数时,将其压numberStack;
            judgeAndPush(c,operatorStack,resultStack);
        }
        //遍历完了,将s1中剩余的运算符依次弹出并压入s2;
        while (!operatorStack.empty()){
            resultStack.push(operatorStack.pop());
        }
        //逆序
        List<Character> list = new ArrayList<>();
        while (!resultStack.empty()){
            list.add(resultStack.pop());
        }
        for (int i = list.size()-1; i >-1; i--) {
            System.out.print(list.get(i) + " ");
        }
    }

    //judge
    public static void judgeAndPush(char c,Stack<Character> operatorStack,Stack<Character> resultStack){
        //这个时候需要写一个判断是否是运算符的方法
        if(isOperator(c)){//运算符
            //如果符号栈为空,直接入栈
            if(operatorStack.empty() || isBracket(operatorStack.peek())==1){
                operatorStack.push(c);
            }else {
                //若优先级比栈顶运算符的高,也将运算符压入符号栈
                //写一个比较符号优先级的方法
                //peek方法是偷窥的意思,知道栈顶是谁,又不使其出栈
                Character top = operatorStack.peek();
                if(getPriority(c) > getPriority(top)){
                    operatorStack.push(c);
                }else {
                    //否则,将符号栈顶的运算符弹出并压入到结果栈中,再次转到(4-1)与符号中新的栈顶运算符相比较
                    resultStack.push(operatorStack.pop());
                    //再次转到(4-1),调用自己
                    judgeAndPush(c,operatorStack,resultStack);
                }
            }
        }else if(isBracket(c)!=0){//括号
            if(isBracket(c)==1){//左括号
                operatorStack.push(c);
            }else {
                while (isBracket(operatorStack.peek())!=1){
                    resultStack.push(operatorStack.pop());
                }
                //这个时候偷窥到(了,要弹出来
                operatorStack.pop();
            }
        }else {
            //是数字
            resultStack.push(c);
        }
    }

    //判断是否是运算符
    public static boolean isOperator(char c){
        return c == '+' || c == '-' || c == '×' || c == '/';
    }

    //判断是否是括号,左括号为1,右括号为2
    public static int isBracket(char c){
        if(c == '('){
            return 1;
        }else if(c == ')'){
            return 2;
        }else {
            return 0;
        }
    }

    //比较符号优先级,+-1 */2
    public static int getPriority(char c){
        switch (c){
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            default:
                throw new RuntimeException("不是符号!" + c);
        }
    }
}

5、运行结果(完美)

(再加上上面的逆波兰计算器,一个完美的计算器就写好了,中缀表达式——后缀表达式——逆波兰计算器)

代码语言:javascript
复制
1 2 3 + 4 × + 5 - 
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2025-01-06,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 0、警醒自己
  • 一、前缀表达式
    • 1、概述
      • 2、前缀表达式的计算求值逻辑
      • 二、中缀表达式
        • 1、概述
        • 三、后缀表达式
          • 1、概述
            • 2、后缀表达式计算求值逻辑
              • 3、逆波兰计算器
                • 表达式:
                • 要求:
                • 代码实现:
                • 运行结果:
            • 四、中缀表达式转后缀表达式【重点】
              • 1、步骤
                • 2、举个例子
                  • 3、说明
                    • 举例子:
                    • 算法 = 武功秘籍:
                    • 掌握算法两重天:
                  • 4、代码实现
                    • 5、运行结果(完美)
                    领券
                    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档