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
}
}