首页 > 其他分享 >10--栈计算器(补充:前缀、中缀、后缀表达式规则;逆波兰表达式计算器)

10--栈计算器(补充:前缀、中缀、后缀表达式规则;逆波兰表达式计算器)

时间:2022-08-16 00:33:23浏览次数:60  
标签:中缀 压入 后缀 运算符 计算器 表达式 String

一、前缀表达式【波兰表达式】

  1. 前缀表达式也称为波兰表达式,其特点是运算符位于操作数之前
  2. 举例说明:(3+4)*5-6 对应的前缀表达式就是:- * + 3 4 5 6

前缀表达式的计算机求值:

从右至左扫描表达式,遇到数字时,将数字压入堆栈中,遇到运算符,弹出来栈顶的2个数,用运算符对他们做相应的运算(栈顶元素和次顶元素),并将结果入栈,重复上述过程直到表达式最左端,最后运算得出的值即为表达式的值,例如(3+4)*5-6 对应的前缀表达式就是:- * + 3 4 5 6,针对前缀表达式求值步骤如下:

  1. 从右至左扫描,将6、5、4、3压入堆栈
  2. 遇到 + 运算符,因此弹出3(栈顶元素)、4(次顶元素),计算出3+4=7,将7入栈
  3. 接下来是 * 运算符,因此弹出7和5,计算出7*5=35,将35入栈
  4. 最后是 - 运算符,计算出 35 - 6 = 29【先弹出来的 - 后弹出来的】,将29入栈 

二、中缀表达式:

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

三、后缀表达式:

  1. 后缀表达式又称为逆波兰表达式,与前缀表达式相似,知识运算符位于操作数之后
  2. 举例说明:(3+4)*5-6 对应的后缀表达式就是:3  4 + 5 * 6 -

后缀表达式计算机求值:

从左至右扫描表达式,遇到数字时,将数字压入栈中,遇到运算符时,弹出栈顶的2个数(栈顶和次顶元素),用运算符将其运算,将其结果压入到栈中,重复上述过程直到表达式的最右端,最后运算出的值即为表达式的值,例如(3+4)*5-6 对应的后缀表达式就是:3  4 + 5 * 6 -,针对其后缀表达式求值的步骤如下:

  1. 从左至右扫描,依次将3、4压入到栈中
  2. 遇到 + 号,弹出4、3,计算3+4=7,将7压入栈中
  3. 将5压入到栈中
  4. 遇到 * 号,弹出5、7,计算5*7=35,将35压入栈中
  5. 将6压入栈中
  6. 最后遇到 - 号,弹出6、35,计算35-6=29,将29压入栈中即为表达式的最终结果

 

案例:完成逆波兰表达式,要求完成如下任务:

  1. 输入一个逆波兰表达式,使用栈(Stack)计算其结果
  2. 支持小括号和多位数整数,【由于此处讲解的是数据结构,因此对计算器进行简化,只支持对整数的计算】
 1 import java.util.ArrayList;
 2 import java.util.List;
 3 import java.util.Stack;
 4 
 5 //逆波兰表达式的计算
 6 public class NiPolandExpression {
 7 
 8     public static void main(String[] args) {
 9         //String expression = "3 4 + 5 * 6 -"; //29
10         //String expression = "30 4 + 5 * 6 -"; //164
11         //中缀:4 * 5 - 8 + 60 + 8 / 2 ==>后缀:4 5 * 8 - 60 + 8 2 / +
12         String expression = "4 5 * 8 - 60 + 8 2 / +"; //76
13         //1、将表达式转成ArrayList集合,后遍历,每遍历一个元素将压栈
14         Stack<String> stack = new Stack<>();
15         List<String> lists = getList(expression);
16         System.out.println(lists);
17         for(String ele: lists) {
18             if (ele.matches("\\d+")) { //正则表达式:表示匹配一个或者多个整数
19                 //是数字直接入栈
20                 stack.push(ele);
21             }else {
22                 //到了这里说明是符号,需要pop出2个操作数
23                 int num2 = Integer.parseInt(stack.pop());
24                 int num1 = Integer.parseInt(stack.pop());
25                 int ret = 0;
26                 switch(ele) {
27                 case "+": 
28                     ret = num1 + num2;
29                     break;
30                 case "-":
31                     ret = num1 - num2;
32                     break;
33                 case "*":
34                     ret = num1 * num2;
35                     break;
36                 case "/":
37                     ret = num1 / num2;
38                     break;
39                     }
40                 //将计算结果压入栈中
41                 stack.push(ret+"");
42             }
43         }
44         int result = Integer.parseInt(stack.pop());
45         System.out.println(expression + "最终结果为:" + result);
46     }
47     
48     public static List<String> getList(String expression){
49         java.util.List<String> lists = new ArrayList<>();
50         String[] arrays = expression.split(" ");
51         for(String ele:arrays) {
52             lists.add(ele);
53         }
54         return lists;
55      }
56     
57 }

 

 

 

 

 

标签:中缀,压入,后缀,运算符,计算器,表达式,String
From: https://www.cnblogs.com/yumengqifei/p/16565516.html

相关文章

  • 2022-08-12第二小组 张晟源(正则表达式)
    JAVA(正则表达式)元字符. :匹配处了换行符之外的任意字符\w:匹配字符或数字或下划线或汉字\s:空格\d:匹配数字\b:匹配单词的开始和结束^:匹配字符串的开始$:匹配字符串的......
  • javascript关于正则表达式
    概述正则表达式是用于字符串匹配的(四个支持正则的方法search查找下标macth查找数组split切割 replace替换)1.正则表达式对象声明1.1new关键词声明varre......
  • Java一次计算简易计算器
    小白简易计算器第一次尝试写代码publicclassCalculator{publicstaticvoidmain(String[]args){//创建扫描对象Scannerscanner=newS......
  • 运算符及表达式
    运算符及表达式//()前面不能直接写++console.log(++(a++));//()不能和++一起使用​​//字符串和数值进行比较(字符串会自动转换为数值)console.log(1>2);//falseconsole.lo......
  • 编写一个简易计算器
    编写一个简易计算器思路用四个方法分别来实现加减乘除使用Scanner进行用户交互利用switch判断运算符 packagecom.ylmxy.method; ​ importjava.util.Sca......
  • day 13 正则表达式
    正则表达式正则表达式的概述正则表达式(RegularExpression)是一个描述字符模式的对象,用于对字符串进行匹配,一般用在有规律的字符串匹配中;常用于表单验证以及相关的......
  • 转:python表达式和语句的区别
    本文摘自:Python表达式和语句之间的区别 表达式是一个值,它的结果一定是一个Python对象。当Python解释器计算它时结果可以是任何对象。例如42,1+2,int(‘123’),range(10)等......
  • 表达式 题解
    零、写在前面\(\texttt{洛谷の题目链接}\)与\(\texttt{Topsの题目链接}\)以及\(\texttt{Hydroの题目链接}\)这道题是\(\texttt{CSP-2020}\)普及组的第三题,但个......