栈---中缀表达式转后缀表达式画图详解和代码实现

淩亂°似流年 2023-07-04 12:54 17阅读 0赞

**中缀表达式转后缀表达式思路步骤分析**：  
1 初始化两个栈：运算符栈s1和存储中间结果的栈s2  
2 从左至右扫描中缀表达式  
3 遇到运算符时，比较其与s1栈顶运算符的优先级

*  3.1 如果s1为空，或栈顶运算符为左括号’(’，则直接将此运算符入栈；
 *  3.2 否则，如果优先级比栈顶运算符的高，也直接将此运算符入栈；
 *  3.3 否则，将s1栈顶的运算符弹出并压入s2中。然后又从3.1步开始进行比较（此时带入栈的操作符还是之前那个，只是栈顶元素已变更）

4 遇到操作数时，将其压入s2  
5 遇到括号时

*  5.1 如果是左括号’(’，则直接压入s1
 *  5.2 如果是右括号’)’，则依次弹出s1栈顶的运算符，并压入s2中，直到遇到左括号’('为止，将这个左括号从s1中弹出丢弃（这时候消除了一对括号）

6 重复2~5步，直到中缀表达式扫描完成  
7 将s1中剩余的运算符依次弹出并压入s2中  
8 依次弹出s2中的元素并输出，并将输出结果逆序，即得到后缀表达式

**以中缀表达式1+((2+3)x4)-5举例**：  
（1）当扫描完1+((2+3后，s1和s2栈元素如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70]  
（2）扫描到一个右括号’)’：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 1]  
（3）扫描到一个乘号和数字4：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 2]  
（4）扫描到一个右括号’)’：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 3]  
（5）扫描到一个减号和5：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 4]  
（6）将s1中剩余的运算符依次弹出并压入s2中  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 5]  
（7）依次弹出s2中的元素并输出，并将输出结果逆序，即得到后缀表达式  
s2出栈：- 5 + x 4 + 3 2 1  
逆序：1 2 3 + 4 x + 5 -

**实现**：

public class SuffixExpressionDemo { 
    
        public static void main(String[] args) { 
            String infixExpression = "1*((23-33)*4)/3";
    
            List<String> suffixExpression = infix2suffixExpression(infixExpression);
            System.out.println("后缀表达式："+suffixExpression);
    
            System.out.println(1*((23-33)*4)/3);
            System.out.println(calculator(suffixExpression));
        }
    
        //中缀表达式转后缀表达式
        public static List<String> infix2suffixExpression(String infixExpression) { 
            List<String> list = string2List(infixExpression); //字符串转成集合
            Stack<String> s1 = new Stack<>(); //存放操作符
            Stack<String> s2 = new Stack<>(); //存放中间结果和数字
            List<String> s2Items = new ArrayList<>(); //存放s2弹出后的元素集
            String result; //结果集
            int i = 0;
            int length = list.size();
            String s; //当前扫描的元素
            String temp;
    
            while(i < length) { 
                s = list.get(i);
    
                if(s.matches("\\d+")) {  //是数字
                    s2.add(s);
                    i++;
                }else{  //是操作符
                    if(s1.isEmpty() || "(".equals(s)) {  //栈顶元素为空或当前元素是左括号
                        s1.add(s);
                        i++;
                    }else if(")".equals(s)){  //当前元素是右括号
                        temp = s1.peek();
                        while(! temp.equals("(")) { 
                            s2.add(s1.pop());
                            temp = s1.peek();
                        }
                        s1.pop();
                        i++;
                    }else{ 
                        String topItem = s1.peek();
                        //栈顶是左括号 或者 当前操作符的优先级比栈顶操作符的高
                        if(topItem.equals("(") || priority(s.charAt(0)) > priority(topItem.charAt(0))) { 
                            s1.add(s);
                            i++;
                        }else{ 
                            //将s1栈顶元素弹出并压入s2
                            s2.add(s1.pop());
                            //注意，这里不能进行i++
                        }
                    }
                }
            }
    
            //将s1剩下的元素压入s2中
            while(! s1.isEmpty()) { 
                s2.add(s1.pop());
            }
            
            //s2栈元素依次弹出
            while(! s2.isEmpty()) { 
                s2Items.add(s2.pop());
            }
    
            Collections.reverse(s2Items);
            return s2Items;
        }
    
        //计算符号的优先级
        public static int priority(char oper) { 
            if(oper == '*' || oper == '/') { 
                return 1;
            }else if(oper == '-' || oper == '+') { 
                return 0;
            }else{ 
                return -1;
            }
        }
    
        //将中缀表达式字符串转成集合
        public static List<String> string2List(String infixExpression) { 
            List<String> list = new ArrayList<>(); //结果集
            int length = infixExpression.length();
            char c; //当前字符
            int j;
            int i = 0;
            while(i < length){ 
                c = infixExpression.charAt(i);
                if(c >= 48 && c <= 57) {  //数字
                    j = i + 1;
                    while(j < length && infixExpression.charAt(j) >=48 && infixExpression.charAt(j) <= 57) { 
                        j++;
                    }
                    list.add(infixExpression.substring(i,j));
                    i = j;
                }else{  //操作符
                    list.add("" + c);
                    i++;
                }
            }
    
            return  list;
        }
    
        //模拟一个简单的计算器
        public static String calculator(List<String> suffixExpression) { 
            Stack<String> stack = new Stack<>();
    
            for (String s : suffixExpression) { 
                if(s.matches("\\d+")) { 
                    stack.add(s);
                }else{ 
                    if(stack.size() < 2) { 
                        throw new RuntimeException("后缀表达式错误");
                    }
                    int n1 = Integer.parseInt(stack.pop());
                    int n2 = Integer.parseInt(stack.pop());
                    switch(s) { 
                        case "*":
                            stack.add(String.valueOf(n2 * n1));
                            break;
                        case "/":
                            stack.add(String.valueOf(n2 / n1));
                            break;
                        case "+":
                            stack.add(String.valueOf(n2 + n1));
                            break;
                        case "-":
                            stack.add(String.valueOf(n2 - n1));
                            break;
                        default:
                            throw new RuntimeException("后缀表达式错误");
                    }
                }
            }
            return stack.pop();
        }
    }

结果：  
![在这里插入图片描述][20200211180545224.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200211141924458.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200211142548245.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200211142410596.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200211142657681.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200211143254214.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200211143203600.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw,size_16,color_FFFFFF,t_70
[20200211180545224.png]: https://img-blog.csdnimg.cn/20200211180545224.png

发表评论取消回复

表情：

评论列表（有 0 条评论，17人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java实现中缀表达式转后缀表达式

Java实现中缀表达式转后缀表达式 1.后缀表达式介绍 1.1简介 1.2实现逆波兰计算器 1.3思路分析 1

ゝ一纸荒年。/ 2024年04月08日 13:54/ 0 赞/ 111 阅读

相关中缀表达式转后缀表达式

算法遍历中缀表达式中的数字和符号：对于数字直接输出对于符号：左括号：进栈运算

阳光穿透心脏的1/2处/ 2023年10月09日 12:50/ 0 赞/ 115 阅读

相关栈---中缀表达式转后缀表达式画图详解和代码实现

中缀表达式转后缀表达式思路步骤分析： 1 初始化两个栈：运算符栈s1和存储中间结果的栈s2 2 从左至右扫描中缀表达式 3 遇到运算符时，比较其与s1栈顶运算符的优

淩亂°似流年/ 2023年07月04日 12:54/ 0 赞/ 18 阅读

相关使用栈实现后缀表达式转中缀表达式

例子例题1 中缀表达式“8+4-6\2” 后缀表达式表示为：8 4 + 6 2 \ - 例题2 中缀表达式：（70 + 30） \20 + 10 / 2

我不是女神ヾ/ 2023年02月12日 05:39/ 0 赞/ 50 阅读

相关使用栈实现中缀表达式转后缀表达式

例子例题1 中缀表达式“8+4-6\2” 后缀表达式表示为：8 4 + 6 2 \ - 例题2 中缀表达式：（70 + 30） \20 + 10 / 2

我就是我/ 2023年02月12日 05:39/ 0 赞/ 54 阅读

相关【代码笔记】【c#】中缀表达式转后缀表达式

/// <summary> /// 中缀表达式转后缀表达式 /// </summary> /// <param name="infi

一时失言乱红尘/ 2022年11月28日 13:18/ 0 赞/ 199 阅读

相关栈应用：中缀表达式转后缀表达式

网上有很多关于中缀转后缀的文章，很多文章或多或少都有bug，包括一些教学视频，经过本人无数次测试，保证下面的代码运算结果的正确性！前提是你写的中缀表达式是正确的哈，没有做中缀表

水深无声/ 2022年06月01日 06:25/ 0 赞/ 298 阅读

相关 [栈] 表达式相关问题代码(C语言)-计算中缀、后缀、前缀表达式|中缀转后缀、前缀表达式

> 本文内容：C语言实现并附有相关讲解 > > 1. 计算中缀表达式 > 2. 计算后缀表达式 > 3. 计算前缀表达式 > 4. 中缀转后缀表达式 > 5. 中缀

今天药忘吃喽~/ 2022年05月15日 05:22/ 0 赞/ 358 阅读

相关中缀转后缀表达式

原理概念： 1. 中缀表达式：符合人们书写习惯的格式如：8+（3-1）\5 2. 后缀表达式：符合计算机运算，如上面对应的后缀表达式：831-5\+

àì夳堔傛蜴生んèń/ 2022年04月13日 02:55/ 0 赞/ 322 阅读

相关中缀转后缀表达式

package com.stack; import java.util.ArrayList; import java.util.List;

缺乏、安全感/ 2021年11月10日 04:04/ 0 赞/ 499 阅读