一、计算器的计算思路分析
我们以计算3+8*2-6 这个算式为例:
-
将算式解析为数字和符号:3,+,8,*,2,-,6
-
准备一个用于存放数字的数字栈numStack,还有一个存放运算符号的符号栈symbolStack,下面分别简称栈n和栈s
-
按顺序扫描解析后的数字和符号,
如果是数字,就直接入数栈n,
如果是符号,且如果符号栈s为空,就直接入栈,
如果s不为空,就需要比较栈顶符号与当前符号的优先级,再分两种情况:
- 如果栈顶符号优先级比当前符号大,就从栈n弹出两个数字,从栈s弹出一个符号,然后进行运算,最后得出的结果再入栈n
- 如果栈顶符号优先级小于或等于当前符号,就将符号入栈s
按照这个流程,扫描完后栈n会留下3,16,6 这三个数,栈s会留下+,- 这两个 符号,
然后按顺序,栈n弹出两个数字,栈s弹出一个符号,然后运算得到结果后再入栈n,重复此步骤,最后栈s清空,栈n只剩一个数字,即为运算结果。
二、代码实现
我们先来实现一个加减乘除的数计算器:
/**
* @Author:黄成兴
* @Date:2020-06-25 16:29
* @Description:使用栈实现一个计算器
*/
public class StackCalculator {
//数字栈
public Stack<Integer> numStack = new Stack<>();
//符号栈
public Stack<String> symbolStack = new Stack<>();
/**
* 根据计算公式运算并输出结果
* @param expression 计算公式
*/
public void calculate(String expression) {
//用于多位数拼接
String numStr = "";
//遍历字符串里的每一个字符
for (int i = 0; i < expression.length() ; i++) {
String ch = expression.substring(i,i + 1);
//检验是否数字
if (ch.matches("[0-9]")) {
//如果该数字已经是最后一个字符就直接存入数字栈
if (i == expression.length() - 1){
numStack.push(Integer.valueOf(ch));
}else {
//如果不是字符串最后一个字符,就拼接入字符串
numStr += ch;
}
continue;
}
//如果是符号,就把之前拼接的多位数存入数字栈
numStack.push(Integer.valueOf(numStr));
numStr = "";
//如果是符号就比较符号优先级
if (isFrist(ch)){
//如果当前符号与符号栈栈栈顶符号优先或者平级就入栈
symbolStack.push(ch);
}else {
//否则就从栈中取两数字和一个符号先计算
int num = getCalculateResult();
//再把计算结果入数栈
numStack.push(num);
//再把当前符号入栈
symbolStack.push(ch);
}
}
//当符号栈为空时,说明计算完成,此时数字栈唯一数字即为结果
while (!symbolStack.empty()) {
int result = getCalculateResult();
numStack.push(result);
}
System.out.println("计算结束!结果为:" + numStack.pop());
}
/**
* 根据数字和符号运算并返回结果
* @param num1 后出栈的数字
* @param num2 先出栈的数字
* @param symbol 运算符号
* @return
*/
public int getCalculateResult(int num1,int num2,String symbol) {
int result = 0;
//根据符号进行运算
switch (symbol){
case "+":
result = num1 + num2;
break;
case "-":
result = num1 - num2;
break;
case "*":
result = num1 * num2;
break;
case "/":
result = num1 / num2;
break;
default:
throw new RuntimeException("只支持加减乘除运算!");
}
System.out.println(num1 + symbol + num2 + "=" + result);
return result;
}
/**
* 直接从数栈取两数字,符号栈取一符号进行计算
* @return
*/
public int getCalculateResult() {
int num1 = numStack.pop();
int num2 = numStack.pop();
String symbol = symbolStack.pop();
int result = getCalculateResult(num2,num1,symbol);
return result;
}
/**
* 比较符号和当前符号栈顶符号的优先级。
* 如果当前符号优先级小于符号栈栈顶符号的优先级,就返回false,否则返回true
* 如果当前符号栈为空,直接返回true
* @param symbol
* @return
*/
public boolean isFrist(String symbol) {
//判断当前符号栈是否为空
if (symbolStack.empty()) {
return true;
}
//取出并放回栈顶符号
String stackSymbol = symbolStack.pop();
symbolStack.push(stackSymbol);
//栈顶符号的优先级
int stackSymbolGrade = getSymbolGrade(stackSymbol);
//当前符号的优先级
int symbolgrade = getSymbolGrade(symbol);
return symbolgrade > stackSymbolGrade;
}
/**
* 根据符号返回符号的优先级
* @param symbol
* @return 加减返回0,乘除返回1
*/
public int getSymbolGrade(String symbol) {
int grade;
if ("+".equals(symbol) || "-".equals(symbol)) {
grade = 0;
} else if ("*".equals(symbol) || "/".equals(symbol)) {
grade = 1;
}else {
throw new RuntimeException("不支持的操作符类型:" + symbol);
}
return grade;
}
}
现在输入运算公式调用calculate() 函数即可得出结果,但是目前这个计算器仍然还有致命问题没有解决:
当连续乘除时无法识别,比如:2*3*3+3 会被识别为(2*3)*(3+3) ,
这个问题下面我们将用递归来解决。
三.、使用递归解决连乘问题
我们分析主函数calculate() 中关于比较符号的代码片段:
//如果是符号就比较符号优先级
if (isFrist(ch)){
//如果当前符号与符号栈栈栈顶符号优先或者平级就入栈
symbolStack.push(ch);
}else {
//否则就从栈中取两数字和一个符号先计算
int num = getCalculateResult();
//再把计算结果入数栈
numStack.push(num);
//再把当前符号入栈
symbolStack.push(ch);
}
可以知道主要问题在于运算符的比较只能进行一次,实际上可能会有连需乘除的情况。
举个例子,要计算1*2*3*4+3 ,+入栈前,数字栈有1234,符号栈有三个*:
- 加号入栈前,取出第一个乘号比较,发现乘法优先,于是取出4和3乘后得12,把12入数栈
- 此时数栈有1,2和12,符号栈有两个*,然后重复步骤1过程,再把乘号取出一个进行比较......
- 步骤2结束后数字栈有1和24,符号栈还有一个*,于是再重复步骤1过程.....
- 最终,符号栈没有比+更优先的符号了,于是加号入栈
以此类推,无论有多少个乘号,实际上的代码都是重复执行步骤1,直到满足进入步骤4的条件时结束。
如果我们把步骤1提取成一个函数,让他执行结束后再调用自己,有几个乘号就让他自己调用几次,那么等到满足步骤4的条件时,也就说明套娃到底了,这时就可以结束调用返回结果。
按照这个思路,我们把原先的代码提取成一个递归方法:
/**
* 使用递归解决连乘或连除问题
* @param symbol
*/
private void compareAndOperation(String symbol) {
//如果是符号就比较符号优先级
if (isFrist(symbol)){
//如果当前符号与符号栈栈栈顶符号优先或者平级就入栈
symbolStack.push(symbol);
return;
}else {
//否则就从栈中取两数字和一个符号先计算
int num = getCalculateResult();
//再把计算结果入数栈
numStack.push(num);
//递归,继续比较上一个是否与当前符号的优先级
compareAndOperation(symbol);
}
}
现在就能计算连续乘除的情况了!
四.完整代码
/**
* @Author:黄成兴
* @Date:2020-06-25 16:29
* @Description:使用栈实现一个计算器
*/
public class StackCalculator {
//数字栈
public Stack<Integer> numStack = new Stack<>();
//符号栈
public Stack<String> symbolStack = new Stack<>();
/**
* 根据计算公式运算并输出结果
* @param expression 计算公式
*/
public void calculate(String expression) {
//用于多位数拼接
String numStr = "";
//遍历字符串里的每一个字符
for (int i = 0; i < expression.length() ; i++) {
String ch = expression.substring(i,i + 1);
//检验是否数字
if (ch.matches("[0-9]")) {
//如果该数字已经是最后一个字符就直接存入数字栈
if (i == expression.length() - 1){
numStack.push(Integer.valueOf(ch));
}else {
//如果不是字符串最后一个字符,就拼接入字符串
numStr += ch;
}
continue;
}
//如果是符号,就把之前拼接的多位数存入数字栈
numStack.push(Integer.valueOf(numStr));
numStr = "";
//如果是符号就比较符号优先级并进行计算和入栈操作
compareAndOperation(ch);
}
//当符号栈为空时,说明计算完成,此时数字栈唯一数字即为结果
while (!symbolStack.empty()) {
int result = getCalculateResult();
numStack.push(result);
}
System.out.println("计算结束!结果为:" + numStack.pop());
}
/**
* 使用递归解决连乘或连除问题
* @param symbol
*/
private void compareAndOperation(String symbol) {
//如果是符号就比较符号优先级
if (isFrist(symbol)){
//如果当前符号与符号栈栈栈顶符号优先或者平级就入栈
symbolStack.push(symbol);
return;
}else {
//否则就从栈中取两数字和一个符号先计算
int num = getCalculateResult();
//再把计算结果入数栈
numStack.push(num);
//递归,继续比较上一个是否与当前符号的优先级
compareAndOperation(symbol);
}
}
/**
* 根据数字和符号运算并返回结果
* @param num1 后出栈的数字
* @param num2 先出栈的数字
* @param symbol 运算符号
* @return
*/
public int getCalculateResult(int num1,symbol);
return result;
}
/**
* 比较符号和当前符号栈顶符号的优先级。
* 如果当前符号优先级小于符号栈栈顶符号的优先级,就返回false,否则返回true
* 如果当前符号栈为空,直接返回true
* @param symbol
* @return
*/
public boolean isFrist(String symbol) {
//判断当前符号栈是否为空
if (symbolStack.empty()) {
return true;
}
//取出并放回栈顶符号
String stackSymbol = symbolStack.pop();
symbolStack.push(stackSymbol);
//栈顶符号的优先级
int stackSymbolGrade = getSymbolGrade(stackSymbol);
//当前符号的优先级
int symbolgrade = getSymbolGrade(symbol);
return symbolgrade > stackSymbolGrade;
}
/**
* 根据符号返回符号的优先级
* @param symbol
* @return 加减返回0,乘除返回1
*/
public int getSymbolGrade(String symbol) {
int grade;
if ("+".equals(symbol) || "-".equals(symbol)) {
grade = 0;
} else if ("*".equals(symbol) || "/".equals(symbol)) {
grade = 1;
}else {
throw new RuntimeException("不支持的操作符类型:" + symbol);
}
return grade;
}
}
(编辑:李大同)
【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!
|