| 失效链接处理 |
|
数据结构java描述 PDF 下载
本站整理下载：
提取码：jkpu
相关截图：
主要内容：
1.1.1.前缀表达式。（波兰表达式）
1.前缀表达式的运算符位于操作数之前。
2.例如：（3+4）×5 -6 对应的前缀表达式位：- × + 3 4 5 6
3.前缀表达式计算机求值：从右往左扫描表达式，遇到数字时，将数字压入栈中，遇到符号时，取出栈的前两个元素进行运算，并将运算结果压入栈中；重复以上过程，直到到达表式的最左侧，最后运算出的结果就是表达式的结果。
1.1.2.中缀表达式。
1.最常见的表达式就是中缀表达式。
2.例如：（3+4）×5-6。
1.1.3.后缀表达式。（逆波兰表达式）
1.运算符位于操作数之后。
2.例如：（3+4）×5-6对应的后缀表达式：34+5×6-。
3.后缀表达式计算机求值：与前缀表达式求值过程相同，不同的只是将后缀表达式从左往右扫描。
4.逆波兰表达式运用：逆波兰计算器。
(1)输入一个逆波兰表达式，使用栈计算其结果。
(2)支持小括号，多位整数。
(3)代码实现
package com.gzk.stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class PolandNotation {
public static void main(String[] args) {
//定义一个逆波兰表达式 (3+4)×5-6 ---> 34+5×6-
String suffixExpression = "30 4 + 5 × 6 -";
List<String> listString = getListString(suffixExpression);
System.out.println("ListStriing + "+listString);
int res = calculate(listString);
System.out.println("计算结果 = "+res);
}
//将一个逆波兰表达式，依次将运算符与数字放入到Arrarylist中
public static List<String> getListString(String suffixExpression){
List<String> list = new ArrayList<String>();
for (String item : suffixExpression.split(" ")) {
list.add(item);
}
return list;
}
//完成逆波兰表达式的运算
public static int calculate(List<String> list) {
Stack<String> stack = new Stack<String>();
for (String item : list) {
//使用正则表达式取出数
if(item.matches("\\d+")) {//item匹配多位数,如果是多位数，则将该数入栈
stack.push(item);
}else {//如果符号，则pop出两个数，并运算
int num2 = Integer.parseInt(stack.pop());
int num1 = Integer.parseInt(stack.pop());
int res = 0;
if(item.equals("+")) {
res = num1+num2;
}else if(item.equals("-")) {
res = num1-num2;
}else if(item.equals("×")) {
res = num2*num1;
}else if(item.equals("/")) {
res = num1/num2;
}else {
throw new RuntimeException("运算符有误～～");
}
stack.push(res+"");
}
}
//最后留在栈中的元素就是结果。
return Integer.parseInt(stack.pop()) ;
}
}
1.1.4.中缀表达式转换后缀表达式
1.具体操作步骤如下：
(1)初始化两个栈，运算符栈s1,和存储中间结果的栈s2.
(2)从左往右扫描中缀表达式。
(3)遇到操作数时将其压入s2中。
(4)遇到运算符时：
①如果s1为空，或栈顶运算符位左括号“（”，则直接将此运算符入栈。
②否则，若优先级比栈顶运算符的高，也将其直接压入栈s1。
③否则，将s1栈顶的运算符并压入s2中，再次转到（4-1）与s1中新的栈顶运算符相比较。
(5)遇到括号时：
①如果是左括号”(“则直接压入栈s1中。
②如果是右括号”)”则依次弹出s1栈顶的运算符，并压入s2,直到遇到左括号为止，此时将这一对括号丢弃。
(6)重复步骤2～5，直到表达式的最右边。
(7)将s1中剩与的运算符依次弹出并压入s2中。
(8)依次弹出s2中的元素并输出，结果的逆序结尾中缀表达式对应的后缀表达式。
|
| Java1234官方群25： | 
|
| Java1234官方群25： | 838462530 |
苏公网安备 32061202001004号
