1、学习不用心,骗人又骗己;
2、学习不刻苦,纸上画老虎;
3、学习不惜时,终得人耻笑;
4、学习不复习,不如不学习;
5、学习不休息,毁眼伤身体;
7、狗才等着别人喂,狼都是自己寻找食物;
①前缀表达式(波兰表达式):前缀表达式又称波兰式,前缀表达式的运算符位于操作数之前;
②举例说明: (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6;
(PS:符号逆序走前面,数字顺序走后面;)
(PS:这么看来前缀表达式就是符号放前面,类似“1+1”就是中缀表达式,那后缀表达式就是将符号放后面(实际上不完全相似,具体见后缀表达式))
从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(栈顶元素 和 次顶元素),并将结果入栈;重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果;
例如:(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,由此得出最终结果;
①中缀表达式就是常见的运算表达式,如(3+4)×5-6;
②中缀表达式的求值是我们人最熟悉的,但是对计算机来说却不好操作(前面我们讲的案例就能看的这个问题),因此,在计算结果时,往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式);
后缀表达式又称逆波兰表达式,与前缀表达式相似,只是运算符位于操作数之后;
中举例说明: (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 + = |
从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 和 栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果;
例如:(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:根据逻辑说明可以很简单地实现计算逻辑,现在的关键问题就是如何将中缀表达式转成后缀表达式了;
正常表达式:a+(b-c)*d —— 逆波兰表达式:a b c – d * +
例如:3+(8-5)*4;
①输入一个逆波兰表达式(后缀表达式),使用栈(Stack), 计算其结果;
②支持小括号和一位整数,因为这里我们主要讲的是数据结构,因此计算器进行简化,只支持对整数的计算;
(使用后缀表达式计算)
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;
}
}
3入栈成功!
8入栈成功!
5入栈成功!
3入栈成功!
4入栈成功!
12入栈成功!
15入栈成功!
最终计算结果:15
①初始化两个栈:运算符栈s1和储存中间结果的栈s2;
②从左至右扫描中缀表达式;
③遇到操作数时,将其压s2;
④遇到运算符时,比较其与s1栈顶运算符的优先级:
如果s1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;
否则,若优先级比栈顶运算符的高,也将运算符压入s1;
否则,将s1栈顶的运算符弹出并压入到s2中,再次转到(4-1)与s1中新的栈顶运算符相比较;
⑤遇到括号时:
(1) 如果是左括号“(”,则直接压入s1;
(2) 如果是右括号“)”,则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃;
⑥重复步骤2至5,直到表达式的最右边;
⑦将s1中剩余的运算符依次弹出并压入s2;
⑧依次弹出s2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式;
举例说明: 将中缀表达 式“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中剩余的运算符 |
我们看到,中缀表达式转后缀表达式实现算法是相当复杂的,我们学习之后运用,很难自创一个这样的新算法;
降龙十八掌:
学习——运用【低层次】;
自创【高层次】;
你是跟着别人的武功秘籍走,还是自创武功,这就是层次的区别!
第一重:学会,然后灵活运用;
第二重:自创,然后发扬光大;
(根据思路自己写出了代码)
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);
}
}
}
(再加上上面的逆波兰计算器,一个完美的计算器就写好了,中缀表达式——后缀表达式——逆波兰计算器)
1 2 3 + 4 × + 5 -