文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Java编程内功-数据结构与算法「前缀,中缀,后缀」

2024-12-03 09:43

关注

 前缀表达式(波兰表达式)

前缀表达式又称波兰表达式,前缀表达式的运算符位于操作符之前,如(3+4)*5-6对应的前缀表达式就是- * + 3 4 5 6

前缀表达式的计算机求值

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

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

  1. 从右至左扫描,将6,5,4,3压入堆栈.
  2. 遇到+运算符,因此弹出3和4(3为栈顶元素,4为次顶元素),计算出3+4的值,得7,再将7入栈.
  3. 接下来是*运算符,因此弹出7和5,计算出35,将35入栈.
  4. 最后是-运算符,计算出35-6的值,即29,由此得出最终结果.

中缀表达式

中缀表达式就是常见的运算表达式,如(3*4)+5-6.中缀表达式的求值是我们人最熟悉的,但是对计算机来说却不好操作,因此在计算结果时,往往会将中缀表达式转换成其他表达式来操作(一般转换成后缀表达式).

后缀表达式

后缀表达式又称为逆波兰表达式,与前缀表达式类似,只是运算符在操作数之后.

如(3+4)*5-6对应的后缀表达式就是3 4 + 5 * 6 -

再比如

后缀表达式的计算机求值

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

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

  1. 从左至右扫描,将3和4压入堆栈.
  2. 遇到+运算符,因此弹出4和3(4为栈顶元素,3为次顶元素),计算出7,再将7入栈.
  3. 将5入栈.
  4. 遇到*运算符,因此单出5和7,计算出35,将35入栈.
  5. 将6入栈.
  6. 最后是-运算符,计算出29,由此得出最终结果.

中缀表达式转后缀表达式

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

从左至右扫描表达式.

遇到操作数时,将其压入s2.

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

  1. 如果s1为空,或者栈顶运算符为左括号"(",则直接将此运算符入栈.
  2. 否则,若优先级比栈顶运算符的高,也将运算符压入s1.
  3. 否则,将s1栈顶的运算符弹出并压入s2中,再次转到(4.1)与s1中新的栈顶运算符相比较.

遇到括号时:

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

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

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

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

简单的后缀表达式计算器

  1. package com.structures.stack; 
  2.  
  3. import java.util.ArrayList; 
  4. import java.util.Arrays; 
  5. import java.util.List; 
  6. import java.util.Stack; 
  7.  
  8. public class PolandNotation { 
  9.     public static void main(String[] args) { 
  10.         //先给出逆波兰表达式(3+4)*5-6==>3 4 + 5 * 6 - 
  11.         String expression = "1+(((2+3)*4))-5"
  12.         List toInfixExpressionList = toInfixExpressionList(expression); 
  13.         System.out.println(toInfixExpressionList); 
  14.         List suffixExpressList = parseSuffixExpressList(toInfixExpressionList); 
  15.         System.out.println(suffixExpressList); 
  16.         System.out.println(calculate(suffixExpressList)); 
  17.          
  18.     } 
  19.  
  20.     //将中缀表达式对应的List转换成后缀表达式对应的List 
  21.     public static List parseSuffixExpressList(List ls) { 
  22.         //定义两个栈 
  23.         Stack s1 = new Stack<>();//符号栈 
  24.  
  25.         //说明:因为s2这个栈,在整个转换过程中,没有pop操作,而且后面还要逆序操作. 
  26.         //因此比较麻烦,这里我们就不用Stack 直接使用List s2. 
  27.         //Stack s2 = new Stack<>();//存储中间结果的栈s2 
  28.         List s2 = new ArrayList<>(); 
  29.         for (String item : ls) { 
  30.             if (item.matches("\\d+")) { 
  31.                 s2.add(item); 
  32.             } else if (item.equals("(")) { 
  33.                 s1.push("("); 
  34.             } else if (item.equals(")")) { 
  35.                 //如果是右括号")",则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃. 
  36.                 while (!s1.peek().equals("(")) { 
  37.                     s2.add(s1.pop()); 
  38.                 } 
  39.                 s1.pop(); 
  40.             } else { 
  41.                 //当item优先级小于等于栈顶运算符,将s1栈顶的运算符弹出并压入s2中,再次转到(4.1)与s1中新的栈顶运算符相比较. 
  42.                 while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) { 
  43.                     s2.add(s1.pop()); 
  44.                 } 
  45.                 //还需要将item压入栈 
  46.                 s1.push(item); 
  47.             } 
  48.         } 
  49.         //将s1中剩余的运算符依次弹出并压入s2 
  50.         while (s1.size() != 0) { 
  51.             s2.add(s1.pop()); 
  52.         } 
  53.         return s2; 
  54.     } 
  55.  
  56.     //将中缀表达式转List 
  57.     public static List toInfixExpressionList(String s) { 
  58.         List ls = new ArrayList<>(); 
  59.  
  60.         int i = 0; 
  61.         String str;//对多位数拼接 
  62.         char c; 
  63.         do { 
  64.             //如果c是一个非数字,直接加入ls 
  65.             if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) < 57) { 
  66.                 ls.add("" + c); 
  67.                 i++; 
  68.             } else { 
  69.                 //如果是一个数,需要考虑多位数问题. 
  70.                 str = ""
  71.                 while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) { 
  72.                     str += c; 
  73.                     i++; 
  74.                 } 
  75.             } 
  76.         } while (i < s.length()); 
  77.         return ls; 
  78.     } 
  79.  
  80.     //根据逆波兰表达式求值 
  81.     public static int calculate(List ls) { 
  82.         Stack stack = new Stack<>(); 
  83.         for (String item : ls) { 
  84.             //这里使用正则表达式来取出数,匹配的是多位数 
  85.             if (item.matches("\\d+")) { 
  86.                 stack.push(item); 
  87.             } else { 
  88.                 int num2 = Integer.parseInt(stack.pop()); 
  89.                 int num1 = Integer.parseInt(stack.pop()); 
  90.                 int res = 0; 
  91.                 switch (item) { 
  92.                     case "+"
  93.                         res = num1 + num2; 
  94.                         break; 
  95.                     case "-"
  96.                         res = num1 - num2; 
  97.                         break; 
  98.                     case "*"
  99.                         res = num1 * num2; 
  100.                         break; 
  101.                     case "/"
  102.                         res = num1 / num2; 
  103.                         break; 
  104.                     default
  105.                         throw new RuntimeException("运算符有误"); 
  106.                 } 
  107.                 stack.push(res + ""); 
  108.             } 
  109.         } 
  110.         return Integer.parseInt(stack.pop()); 
  111.     } 
  112.  
  113. //根据运算符返回对应的优先级数字 
  114. class Operation { 
  115.     private static int ADD = 1; 
  116.     private static int SUB = 1; 
  117.     private static int MUL = 2; 
  118.     private static int DIV = 2; 
  119.  
  120.     public static int getValue(String operation) { 
  121.         int result = 0; 
  122.         switch (operation) { 
  123.             case "+"
  124.                 result = ADD
  125.                 break; 
  126.             case "-"
  127.                 result = SUB; 
  128.                 break; 
  129.             case "*"
  130.                 result = MUL; 
  131.                 break; 
  132.             case "/"
  133.                 result = DIV; 
  134.                 break; 
  135.             default
  136.                 System.out.println("不存在该运算符"); 
  137.                 break; 
  138.         } 
  139.         return result; 
  140.     } 

 【编辑推荐】

  1. 5分钟让你理解K8S必备架构概念,以及网络模型
  2. 92年百度程序员被抓,给我们警示什么?
  3. 开源云盘利器:Nextcloud 21私有云盘搭建
  4. 更纯净,微软 Windows10 21H2 重大更新将减少系统臃肿软件数量
  5. 996工作制究竟是好是坏?

 

来源:今日头条内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯