一、前缀表达式【波兰表达式】:
- 前缀表达式也称为波兰表达式,其特点是运算符位于操作数之前
- 举例说明:(3+4)*5-6 对应的前缀表达式就是:- * + 3 4 5 6
前缀表达式的计算机求值:
从右至左扫描表达式,遇到数字时,将数字压入堆栈中,遇到运算符,弹出来栈顶的2个数,用运算符对他们做相应的运算(栈顶元素和次顶元素),并将结果入栈,重复上述过程直到表达式最左端,最后运算得出的值即为表达式的值,例如(3+4)*5-6 对应的前缀表达式就是:- * + 3 4 5 6,针对前缀表达式求值步骤如下:
- 从右至左扫描,将6、5、4、3压入堆栈
- 遇到 + 运算符,因此弹出3(栈顶元素)、4(次顶元素),计算出3+4=7,将7入栈
- 接下来是 * 运算符,因此弹出7和5,计算出7*5=35,将35入栈
- 最后是 - 运算符,计算出 35 - 6 = 29【先弹出来的 - 后弹出来的】,将29入栈
二、中缀表达式:
- 中缀表达式就是我们常见的表达式:如(3+4)*5-6
- 中缀表达式的求值是我们最熟悉的,但是对于计算机来说并不好操作,因此,在计算结果时,往往会将中缀表达式转成其它表达式来操作【一般转成后缀表达式】
三、后缀表达式:
- 后缀表达式又称为逆波兰表达式,与前缀表达式相似,知识运算符位于操作数之后
- 举例说明:(3+4)*5-6 对应的后缀表达式就是:3 4 + 5 * 6 -
后缀表达式计算机求值:
从左至右扫描表达式,遇到数字时,将数字压入栈中,遇到运算符时,弹出栈顶的2个数(栈顶和次顶元素),用运算符将其运算,将其结果压入到栈中,重复上述过程直到表达式的最右端,最后运算出的值即为表达式的值,例如(3+4)*5-6 对应的后缀表达式就是:3 4 + 5 * 6 -,针对其后缀表达式求值的步骤如下:
- 从左至右扫描,依次将3、4压入到栈中
- 遇到 + 号,弹出4、3,计算3+4=7,将7压入栈中
- 将5压入到栈中
- 遇到 * 号,弹出5、7,计算5*7=35,将35压入栈中
- 将6压入栈中
- 最后遇到 - 号,弹出6、35,计算35-6=29,将29压入栈中即为表达式的最终结果
案例:完成逆波兰表达式,要求完成如下任务:
- 输入一个逆波兰表达式,使用栈(Stack)计算其结果
- 支持小括号和多位数整数,【由于此处讲解的是数据结构,因此对计算器进行简化,只支持对整数的计算】
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