5.5 、栈实现综合计算器(中缀表达式)
使用栈来实现综合计算器
思路分析(图解)
- 思路分析：如何使用栈完成计算一个表达式的结果？（由于原表达式过长，演示需要时间所以换成第二个表达式）
- 1、通过一个index值（索引），来遍历我们的表达式
- 2、如果发现是一个数字，就直接入数栈
- 3、如果发现扫描到的是一个符号，就分成以下两种情况
- 3.1、如果发现当前的符号栈为空，就直接入栈
- 3.2、如果符号栈有操作符时，就与栈中的操作符进行比较，如果当前的操作符的优先级小于或者等于栈中的操作符，这时就需要从数栈中pop中两个数，再重符号栈中pop中符号（即运算符）进行运算，将得到的运行结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大于栈中的操作符，就直接入栈（符号栈）。
- 4、当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运算
- 5、最后数栈只有一个数组就是这个表达式的结果
- 验证表达式：3+2*6-2 = ？
代码实现：[1. 先实现一位数的运算， 2. 扩展到多位数的运算]
- 这里复用前面使用数组模拟栈的代码，并在原功能上进行加强
- 即加上运算符优先级、判断是不是运算符和计算的方法
public class ArrayStack2 {
private int maxSize; //栈的大小
private int[] stack; //数组，数组模拟栈，数据就放在该数组中
private int top = -1; //top表示栈顶，初始值为-1
//构造器
public ArrayStack2(int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
}
//模拟栈满
public boolean isFull() {
return top == maxSize - 1;
}
//模拟栈空
public boolean isEmpty() {
return top == -1;
}
//模拟入栈
public void push(int value) {
//先判断栈是否满
if (isFull()) {
System.out.println("栈满");
}
top++;
stack[top] = value;
}
//模拟出栈,将栈顶的数据返回
public int pop() {
//先判断栈是否空
if (isEmpty()) {
//抛出异常
throw new RuntimeException("栈空,没有数据");
}
//先取得栈顶的值
int value = stack[top];
top--;
return value;
}
//显示栈的情况（遍历栈）,由于栈是先入后出，所以要从栈底开始遍历
public void list() {
if (isEmpty()) {
System.out.println("栈空，没有数据");
}
//需要从栈顶开始显示数据
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}
//返回运算符的优先级，优先级是程序员来确定的，优先级使用数字表示，数字越大，优先级越高
public int priority(int oper) {
if (oper == '*' || oper == '/') {
return 1;
} else if (oper == '+' || oper == '-') {
return 0;
} else {
return -1; //假定目前表达式只有加减乘除四种运算符
}
}
//判断是不是一个运算符的方法
public boolean isOper(char val) {
return val == '+' || val == '-' || val == '*' || val == '/';
}
//计算方法
public int cal(int num1,int num2,int oper){
int result = 0; //用于存放计算的结果
switch (oper){
case '+':
result = num1 + num2;
break;
case '-':
result = num2 - num1;
break;
case '*':
result = num1 * num2;
break;
case '/':
result = num2 / num1;
break;
}
return result;
}
//可以返回当前栈顶的值，但是不是真正的出栈
public int peek(){
return stack[top];
}
}
接下来就开始测试了
public class Calculator {
public static void main(String[] args) {
//根据思路，完成表达式的运算
String expression = "3+2*6-2";
//创建两个栈，一个数栈一个符号栈
ArrayStack2 numStack = new ArrayStack2(10);
ArrayStack2 operStack = new ArrayStack2(10);
//定义需要的相关变量
int index = 0; //用于扫描表达式中的数字和运算符
int num1 = 0; //计算的数字1
int num2 = 0; //计算的数字2
int oper = 0; //运算符
int result = 0; //接收结果
char ch = ' '; //将每次扫描得到的char保存到ch中
//开始使用while循环扫描expression
while (true){
//一次得到expression里的每一个字符
ch = expression.substring(index,index+1).charAt(0);
//判断ch是什么然后做相应的处理
if (operStack.isOper(ch)){ //如果是运算符
//判断当前符号栈是否为空
if (!operStack.isEmpty()){
//如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中的操作符
if (operStack.priority(ch)<= operStack.priority(operStack.peek())){
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
result = numStack.cal(num1, num2,oper);
//把运算的结果入数栈
numStack.push(result);
//把当前的操作符入符号栈
operStack.push(ch);
} else {
//如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈
operStack.push(ch);
}
}else {
//如果为空直接入符号栈
operStack.push(ch);
}
}else { //如果是数,则直接入数栈
numStack.push(ch-48);
}
//让index+1，并判断是否扫描到expression最后
index++;
if (index>=expression.length()){
break;
}
}
//当表达式扫描完毕，就顺序从数栈和符号栈中pop出相应的数和符号，并运行
while (true){
//如果符号栈为空，则计算到最后的结果，数栈中只有一个数字[结果]
if (operStack.isEmpty()){
break;
}
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
result = numStack.cal(num1, num2,oper);
numStack.push(result); //入栈
}
//将数栈的最后数pop出来，就是结果
int result2 = numStack.pop();
System.out.printf("表达式%s = %d",expression,result2);
}
}
经测试，完成了单位数运算
但是又有一个新问题，即双位数参与运算就会导致运算结果不正确
所以要对代码进行再次优化，即在扫描数时加上逻辑
else { //如果是数,则直接入数栈
/*
numStack.push(ch-48);
分析思路
1、当处理多位数时，不能发现是一个数就立即入栈，因为它可能是多位数
2、在处理数时，需要向expression的表达式的后面index后再看一位，如果是数就继续扫描，如果是符号才入栈
3、因此我们需要定义一个字符串变量，用于拼接
处理多位数
*/
keepNum += ch;
//如果ch以及是expression的最后一位，就直接入栈
if (index == expression.length() - 1) {
numStack.push(Integer.parseInt(keepNum));
} else {
//判断下一个字符是不是数字，如果是数字就继续扫描，如果是运算符则入栈,注意是看后一位，不是index++
if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
//如果后一位是运算符则入栈
numStack.push(Integer.parseInt(keepNum));
//重要的清空，keepNum清空
keepNum = "";
}
}
}
5.6 、逆波兰计算器
我们完成一个逆波兰计算器，要求完成如下任务:
1) 输入一个逆波兰表达式(后缀表达式)，使用栈(Stack), 计算其结果
2) 支持小括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算。
3) 思路分析
- 例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:
- 1．从左至右扫描，将 3 和 4 压入堆栈；
- 2．遇到+运算符，因此弹出 4 和 3（4 为栈顶元素，3 为次顶元素），计算出 3+4 的值，得7，再将7 入栈；
- 3．将 5 入栈；
- 4．接下来是×运算符，因此弹出 5 和 7，计算出 7×5=35，将 35 入栈；
- 5．将 6 入栈；
- 6．最后是-运算符，计算出 35-6 的值，即 29，由此得出最终结果
4) 代码实现：
public class PolandNotationStack {
public static void main(String[] args) {
//1、先定义一个逆波兰表达式, (3+4) * 5 -6 --> 3 4 + 5 * 6 - （使用空格隔开）
String suffixExpression = "3 4 + 5 * 6 -";
//测试结果
List<String> list = getListString(suffixExpression);
int result = calculate(list);
System.out.println("计算的结果=" + result);
}
//2、定义一个方法，依次将数据和运算符放入 ArrayList中
public static List<String> getListString(String suffixExpression) {
//3、将逆波兰表达式进行分隔（即使用空格进行分隔）
String[] split = suffixExpression.split(" ");
List<String> list = new ArrayList<String>();
//4、使用for循环对数组split进行遍历，每循环一次就取出字符串中的一个元素
for (String ele : split) {
list.add(ele);
}
//4.1、遍历完成后再将数组返回
return list;
}
//4.2、创建一个栈
public static int calculate(List<String> list) {
Stack<String> stack = new Stack<>();
//4.3、遍历
for (String item : list) {
//5.1、从左至右扫描,使用正则表达式取出数
if (item.matches("\\d+")) { //代表匹配的是多位数
//5.2、扫描到元素内有数直接入栈
stack.push(item);
} else {
//6、遇到运算符，因此pop栈顶元素和为次顶元素，计算出值
int num2 = Integer.parseInt(stack.pop());
int num1 = Integer.parseInt(stack.pop());
int result = 0; //6.1、定义一个存放结果的值
if (item.equals("+")) { //加法
result = num1 + num2;
} else if (item.equals("-")) { //减法
result = num1 - num2;
} else if (item.equals("*")) { //乘法
result = num1 * num2;
} else if (item.equals("/")) { //除法
result = num1 / num2;
} else {
//若不是加减乘除就抛出异常
throw new RuntimeException("运算符有误");
}
//6.1、再将计算结果入栈
stack.push(result + "");
}
}
//7、最后留在栈中的数就是结果
return Integer.parseInt(stack.pop());
}
}
5.7 、中缀表达式转换为后缀表达式
后缀表达式适合计算式进行运算，但是人却不太容易写出来，尤其是表达式很长的情况下，因此在开发中，我们需要将 中缀表达式转成后缀表达式。
5.7.1、具体步骤如下
- 1) 初始化两个栈：运算符栈 s1 和储存中间结果的栈 s2；
- 2) 从左至右扫描中缀表达式；
- 3) 遇到操作数时，将其压 s2；
- 4) 遇到运算符时，比较其与 s1 栈顶运算符的优先级：
- 1.如果 s1 为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
- 2.否则，若优先级比栈顶运算符的高，也将运算符压入 s1；
- 3.否则，将 s1 栈顶的运算符弹出并压入到 s2 中，再次转到(4-1)与 s1 中新的栈顶运算符相比较；
- 5) 遇到括号时：
- (1) 如果是左括号“(”，则直接压入 s1
- (2) 如果是右括号“)”，则依次弹出 s1 栈顶的运算符，并压入 s2，直到遇到左括号为止，此时将这一对括号丢弃
- 6) 重复步骤 2 至 5，直到表达式的最右边
- 7) 将 s1 中剩余的运算符依次弹出并压入 s2 8) 依次弹出 s2 中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
- 8) 依次弹出 s2 中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
5.7.2、举例说明:
将中缀表达式“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中剩余的运算符 |
5.7.3、代码实现中缀表达式转为后缀表达式
思路分析：
中缀表达式 1 + ( ( 2 + 3 )× 4) - 5 =》 后缀表达式
将 s2 出栈 - 5 + * 4 + 3 2 1 => 1 2 3 + 4 * + 5 -
中缀表达式 转 后缀表达式的 思路步骤分析
打比方 ： 降龙十八掌 ：学习 -》 应用 [层次]
算法 -》第一个层面： 理解算法-》灵活运用算法
第二层： 设计算法-》 运用 【】
1) 初始化两个栈：运算符栈s1和储存中间结果的栈s2；
2) 从左至右扫描中缀表达式；
3) 遇到操作数时，将其压s2；
4) 遇到运算符时，比较其与s1栈顶运算符的优先级：
1.如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
2.否则，若优先级比栈顶运算符的高，也将运算符压入s1；
3.否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较；
5) 遇到括号时：
(1) 如果是左括号“(”，则直接压入s1
(2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃6) 重复步骤2至5，直到表达式的最右边
7) 将s1中剩余的运算符依次弹出并压入s2
8) 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
代码实现入下：
/**
* 完成一个将中缀表达式转成后缀表达式的功能
* 说明：1、1 +（（2+3）* 4）-5 --> 转成 1 2 3 + 4 * + 5 -
* 2、直接对字符串操作不方便，因此先将"1 +（（2+3）* 4）-5"-->中缀表达式转换成对应的List
* 即 "1 +（（2+3）* 4）-5" --> ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
*/
public class PolandNotationStackTwo {
public static void main(String[] args) {
String expression = "1+((2+3)*4)-5";
//测试功能是否正常
List<String> list = toInfixExpressionList(expression);
System.out.println(list); //[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
}
//1、首先编写一个方法，将中缀表达式转成对应的List
public static List<String> toInfixExpressionList(String s) {
//2、定义一个List，存放中缀表达式对应的内容
List<String> list = new ArrayList<>();
int i = 0; //用于遍历中缀表达式字符串
String str; //用于对多位数的拼接
char c; //每遍历到一个字符，就放入到c中
do {
//如果c是非数字，就需要加入到list中
if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
list.add("" + c);
i++; //i需要后移
} else { //如果是一个数，需要考虑多位数的问题
str = ""; //先将str置空
while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
str += c; //拼接
i++;
}
list.add(str);
}
} while (i < s.length());
return list; //返回
}
}
/**
* description
* 可以返回一个运算符对应的优先级
*
* @author
* @since 2022/11/18 10:04
*/
public class Operation {
private static int ADD = 1;
private static int SUB = 1;
private static int MUL = 2;
private static int DIV = 2;
//编写一个方法，返回对应的优先级数字
public static int getValue(String operation) {
int result = 0;
switch (operation){
case "+":
result = ADD;
break;
case "-":
result = SUB;
break;
case "*":
result = MUL;
break;
case "/":
result = DIV;
break;
default:
System.out.println("不存在该运算符");
}
return result;
}
}
/**
* 完成一个将中缀表达式转成后缀表达式的功能
* 说明：1、1 +（（2+3）* 4）-5 --> 转成 1 2 3 + 4 * + 5 -
* 2、直接对字符串操作不方便，因此先将"1 +（（2+3）* 4）-5"-->中缀表达式转换成对应的List
* 即 "1 +（（2+3）* 4）-5" --> ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
*/
public class PolandNotationStackTwo {
public static void main(String[] args) {
String expression = "1+((2+3)*4)-5";
//测试功能是否正常
List<String> list = toInfixExpressionList(expression);
System.out.println("中缀表达式对应的List=" +list); //[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
List<String> parseSuffixExpressionList = parseSuffixExpressionList(list);
System.out.println("后缀表达式对应的List= "+ parseSuffixExpressionList);
}
//1、首先编写一个方法，将中缀表达式转成对应的List
public static List<String> toInfixExpressionList(String s) {
//2、定义一个List，存放中缀表达式对应的内容
List<String> list = new ArrayList<>();
int i = 0; //用于遍历中缀表达式字符串
String str; //用于对多位数的拼接
char c; //每遍历到一个字符，就放入到c中
do {
//如果c是非数字，就需要加入到list中
if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
list.add("" + c);
i++; //i需要后移
} else { //如果是一个数，需要考虑多位数的问题
str = ""; //先将str置空
while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
str += c; //拼接
i++;
}
list.add(str);
}
} while (i < s.length());
return list; //返回
}
//3、将得到的中缀表达式对应的List转成后缀表达式对应的List
public static List<String> parseSuffixExpressionList(List<String> list) {
//4、定义两个栈
Stack<String> s1 = new Stack<>(); //符号栈
//4.1、说明：因为s2在整个转换过程中没有pop操作，而且最后还需要逆序输出，因此为了简化使用List替代
List<String> s2 = new ArrayList<String>(); //存放中间结果
//5、遍历中缀表达式对应的List
for (String item : list) {
//6、如果是一个数，加入到s2，使用正则表达式判断是否是数
if (item.matches("\\d+")) {
s2.add(item);
} else if (item.equals("(")) {
//6.1如果是左括号，直接入s1符号栈
s1.push(item);
} else if (item.equals(")")) {
//6.2、 如果是右括号，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
while (!s1.peek().equals("(")) {
s2.add(s1.pop());
}
s1.pop(); //将（ 弹出 s1这个栈，消除小括号
} else {
//6.3、当item的优先级小于等于s1栈顶运算符的优先级，将s1栈顶的运算符弹出并加入到s2中，再次转到与s1中新的栈顶运算符相比较
while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
s2.add(s1.pop());
}
//6.4、还需要将item压入栈中
s1.push(item);
}
}
//7、将s1剩余的运算符依次弹出并加入s2中
while (s1.size() != 0){
s2.add(s1.pop());
}
return s2; //注意，因为是存放到List中，因此按顺序输出就是后缀表达式对应的List
}
}
