0. 准备工作：
(1) 一个用来存储数值的数值栈：numStack
(2) 一个用来存储运算符的运算符栈：operStack
1. 将字符串表达式拆分，然后逐个扫描。
(1) 如果是数字，直接压入数值栈
(2) 如果是运算符
1 如果当前运算符栈为空，直接将运算符压入运算符栈
2 如果运算符不为空
1) 如果当前运算符的优先级高于运算符栈栈顶的运算符，则直接压入运算符栈
2) 如果当前运算符的优先级小于或等于运算符栈栈顶的运算符，则需要将栈顶的运算符弹出，同时需要从数值栈中弹出两个数，与栈顶运算与进行运算，然后将运算结果重新压入数值栈。最后继续判断当前运算符与栈顶运算符的优先级，重复该步骤。
2. 表达式扫描完成后，如果运算符栈不为空，则弹出栈顶运算符，同时弹出数值栈中的两个数，进行运算，将结果重新压入数值栈，直到运算符栈为空，此时数值栈中的最后一个数值即为表达式的运算结果。
表达式入栈原理图解
表达式为：2*3*2+4-5-6*2，首先将表达式拆分为
"2"，"*"，"3"，"*"，"2"，"+"，"4"，"-"，"5"，"-"，"6"，"*"，"2"
1. 扫描第一个字符串，判断为数字 "2"，直接压入数值栈
2. 扫描第二个字符串，判断为运算符"*"，运算符栈为空，直接压入运算符栈
3. 扫描第三个字符串，判断为数字"3"，直接压入数值栈
4. 扫描第四个字符串，判断为运算符"*"，运算符栈不为空，与栈顶的运算符 * 优先级相等，需要进行运算
1） 首先弹出运算符栈栈顶的 *
2） 弹出数值栈中的 3
3） 弹出数值栈中的 2
4） 将 3 * 2 的结果重新压入数值栈
5） 将第四个字符串的*压入运算符栈
5. 扫描第五个字符串，判断为数值"2"，直接压入数值栈
6. 扫描第六个字符串，判断为运算符 "+"，继续与运算符栈顶进行优先级比较。结果为小于
1） 首先弹出运算符栈栈顶的 *
2） 弹出数值栈中的 2
3） 弹出数值栈中的 6
4） 将 2 * 6 的结果重新压入数值栈
5） 将第六个字符串的+压入运算符栈
7. 扫描第七个字符串，判断为数值"4"，直接入数值栈
8. 扫描第八个字符串，判断为运算符 "-"，继续与运算符栈顶进行优先级比较。结果为等于
9. 扫描第九个字符串，判断为数值"5"，直接入数值栈
10. 扫描第十个字符串，判断为运算符 "-"，继续与运算符栈顶进行优先级比较。结果为等于
1） 首先弹出运算符栈栈顶的 -
2） 弹出数值栈中的 5
3） 弹出数值栈中的 16
4） 将 16 - 5 的结果重新压入数值栈
5） 将第十个字符串的-压入运算符栈
11. 扫描第十一个字符串，判断为数值"6"，直接入数值栈
12. 扫描第十二个字符串，判断为运算符 "*"，继续与运算符栈顶进行优先级比较。结果为大于
13. 扫描第十三个字符串，判断为数值"2"，直接入数值栈
表达式解析入栈过程
计算过程图解
表达式为：2*3*2+4-5-6*2，解析完成后，栈内情况如下图所示
重复如下步骤，直到运算符栈为空：
1） 从 operStack 栈弹出一个运算符
2） 从 numStack 栈弹出两个数据
3） 计算结果后将结果重新压入数值栈
中缀表达式计算器代码实现
/**
* All rights Reserved, Designed By https://www.tulingxueyuan.com/
* @Title: MyCalculator.java
* @Package com.tuling.calculator
* @Description:
* @author: 小白
* @Date 2019年12月3日 下午3:28:03
* @version V1.0
* @Copyright:
*/
package com.tuling.calculator;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
/**
* @ClassName MyCalculator
* @Description 中缀表达式实现计算器
* @Author 北京图灵学院
* @Date 2019年12月3日 下午3:28:03
*/
public class MyCalculator {
//数值栈
private MyStack numStack;
//运算符栈
private MyStack operStack;
//ArrayList 用来存放表达式拆分后的字符串
private List<String> sourceExp;
/**
* @Title: MyCalculator
* @Description:
* @param:
* @throws
*/
public MyCalculator() {
numStack = new MyStack(10);
operStack = new MyStack(10);
sourceExp = new ArrayList<String>();
}
/**
*
* @Title: calculate
* @Description:计算
* @param: @param expression
* @param: @return
* @return: int
* @throws
*/
public int calculate(String expression) {
//先将原始表达式拆分
getExp(expression);
//将原始表达式逐个解析，入栈
inStack(sourceExp);
//入栈完成，依次从运算符栈弹出一个运算符，从数值栈弹出两个数，进行运算。
while(!operStack.isEmpty()) {
//弹出当前运算符栈顶的运算符
String oper = operStack.pop();
String num1 = numStack.pop();
String num2 = numStack.pop();
//计算结果
int result = cal(Integer.parseInt(num1), Integer.parseInt(num2), oper);
//将结果压入数值栈
numStack.push(result+"");
}
//将数值栈的数返回。
return Integer.parseInt(numStack.pop());
}
/**
* @param list
* @Title: inStack
* @Description:将原始表达式逐个解析，进行入栈操作
* 遍历集合，拿到每一个元素并且判断
* 1.如果是运算符
* 1.1> 如果当前运算符栈不为空：
* 1.1.1> 如果当前运算符的优先级小于或者等于栈顶的运算符优先级
* 从数值栈中弹出两个数，并且将运算的结果压入数值栈
* 将运算符压入运算符栈
* 1.1.2> 否则：直接压入运算符栈
* 1.2> 如果当前运算符栈为空：直接压入运算符栈
* 2.如果是数值：
* 直接压入数值栈
* @param:
* @return: void
* @throws
*/
private void inStack(List<String> list) {
for(String str:list) {
if(isOper(str)) {
//判断
if(operStack.isEmpty()) {
//运算符栈为空，直接入栈
operStack.push(str);
}else {
//不为空，需要与栈顶运算符比较优先级高低
//如果当前运算符的优先级小于或等于运算符栈顶的优先级，需要运算
if(priority(str) <= priority(operStack.peek())) {
//需要运算，
//弹出当前运算符栈顶的运算符
String oper = operStack.pop();
String num1 = numStack.pop();
String num2 = numStack.pop();
//计算结果
int result = cal(Integer.parseInt(num1), Integer.parseInt(num2), oper);
//将结果压入数值栈
numStack.push(result+"");
//将运算符压入运算符栈
operStack.push(str);
}else if(priority(str) > priority(operStack.peek())) {
//直接入运算符栈
operStack.push(str);
}
}
}else if(isNum(str)) {
//数字，直接入数值栈
numStack.push(str);
}
}
}
public int cal(int num1,int num2,String 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;
default:
break;
}
return result;
}
/**
*
* @Title: priority
* @Description:返回运算符的优先级
* @param: @param oper
* @param: @return
* @return: int
* @throws
*/
public int priority(String oper) {
switch (oper) {
case "*":
case "/":
return 2;
case "+":
case "-":
return 1;
default:
return 0;
}
}
/**
* @Title: isNum
* @Description:判断是否为数字
* @param: @param str
* @param: @return
* @return: boolean
* @throws
*/
private boolean isNum(String str) {
return str.matches("[0-9]+");
}
/**
* @Title: isOper
* @Description:判断是否为运算符
* @param: @param str
* @param: @return
* @return: boolean
* @throws
*/
private boolean isOper(String str) {
return str.matches("[\\+\\-\\*\\/]");
}
/**
* @Title: getExp
* @Description:将原始表达式拆分为字符串
* @param: @param expression
* @return: void
* @throws
*/
private void getExp(String expression) {
StringTokenizer stringTokenizer = new StringTokenizer(expression, "+-*/", true);
while(stringTokenizer.hasMoreTokens()) {
sourceExp.add(stringTokenizer.nextToken());
}
}
}
测试类代码如下：
/**
* All rights Reserved, Designed By https://www.tulingxueyuan.com/
* @Title: Test.java
* @Package com.tuling.calculator
* @Description:
* @author: 小白
* @Date 2019年12月3日 下午7:28:33
* @version V1.0
* @Copyright:
*/
package com.tuling.calculator;
/**
* @ClassName Test
* @Description
* @Author 北京图灵学院
* @Date 2019年12月3日 下午7:28:33
*/
public class Test {
/**
* @Title: main
* @Description:
* @param: @param args
* @return: void
* @throws
*/
public static void main(String[] args) {
// String expression = "2+3*4";
String expression = "2*3*4+5-6-4*2";
MyCalculator mc = new MyCalculator();
int result = mc.calculate(expression);
System.out.println("表达式：" + expression + " = " + result);
}
} 版权声明：本文内容由互联网用户贡献，该文观点仅代表作者本人。本站不拥有所有权，不承担相关法律责任。如发现有侵权/违规的内容， 联系QQ15101117，本站将立刻清除。
