栈实现综合计算器(中缀表达式)
程序员文章站
2022-05-26 12:01:55
...
1.使用栈来实现综合计算器
请输入一个表达式
计算式:[722-5+1-5+3-3] 点击计算
2.思路分析:
3.代码实现(1.先实现1位数的运算;2.再扩展到多位数的运算)
package com.itguigu.stack;
/**
* 使用栈完成表达式的计算
* 思路分析:
* 1.通过一个index值,来遍历我们的表达式;
* 2.创建两个栈:数栈和符号栈,如果扫描发现是数字,直接加入数栈
* 3.如果扫描发现是符号,分以下情况:
* (1).如果符号栈为空,直接将扫描到的符号加入符号栈;
* (2).如果符号栈不为空,分以下情况:
* 1).如果扫描到的符号大于符号栈中的符号,直接将扫描到的符号加入符号栈;
* 2).如果扫描到的符号小于等于符号栈中的符号,就从数栈中pop出两个数,从符号栈中pop出一个
* 符号,进行计算,将得到的结果加入到数栈,然后将之前扫描到的符号加入到符号栈
* 4.当表达式扫描完成,就顺序的从数栈和符号栈中pop出相应的数和符号,并运算;
* 5.最后在数栈中只有一个数,这个数就是表达式的结果
*/
public class Calculator {
public static void main(String[] args) {
String expression = "13+2*6-2";
int index = 0; // 通过一个index值,来遍历我们的表达式
int res = 0; // 用于存放结果
int oper = 0;// 用于存放运算符
int num1 = 0;
int num2 = 0;
char ch = ' '; // 用于存放每次扫描到的结果
String keepNum = "";// 用于拼接字符串
// 创建两个栈:数栈和符号栈,如果扫描发现是数字,直接加入数栈
ArrayStack2 numStack = new ArrayStack2(10);
ArrayStack2 operStack = new ArrayStack2(10);
// 进行扫描
while (true) {
ch = expression.substring(index, index + 1).charAt(0);
// 判断扫描到的结果,调用isOper()方法,如果是运算符则返回true
if (operStack.isOper(ch)) { // 是运算符
// 判断符号栈是否为空
if (!operStack.isEmpty()) { // 不为空
// 如果符号栈不为空,分以下情况:
// * 1).如果扫描到的符号大于符号栈中的符号,直接将扫描到的符号加入符号栈;
// * 2).如果扫描到的符号小于等于符号栈中的符号,就从数栈中pop出两个数,从符号栈中pop出一个
// 符号,进行计算,将得到的结果加入到数栈,然后将之前扫描到的符号加入到符号栈
if (operStack.priority(ch) <= operStack.priority(operStack.peek())) { // 小于等于
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1, num2, oper);
numStack.push(res);
operStack.push(ch);
} else { // 大于
operStack.push(ch);
}
} else { // 为空
// 如果符号栈为空,直接将扫描到的符号加入符号栈;
operStack.push(ch);
}
} else { // 是数
/**
* 如果扫描发现是数字,直接加入数栈(弊端:只能是一位数)
*/
// numStack.push(ch -48);
/**
* 在处理多位数时,需要向expression的表达式的index后看一位,如果是数就继续扫描,如果是符号就直接添加
*/
keepNum += ch;
if (index == expression.length() - 1) { // 到了表达式的最后一位,直接添加
numStack.push(Integer.parseInt(keepNum));
} else {
if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
numStack.push(Integer.parseInt(keepNum));
keepNum = "";
}
}
}
index++;
if (index >= expression.length()) {
break;
}
}
// 当表达式扫描完成,就顺序的从数栈和符号栈中pop出相应的数和符号,并运算;
while (true) {
// 当符号栈为空,表示计算完毕
if (operStack.isEmpty()) {
break;
}
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1, num2, oper);
numStack.push(res);
}
// 最后在数栈中只有一个数,这个数就是表达式的结果
int re = numStack.pop();
System.out.println(expression + "的计算结果为: " + re);
}
}
/**
* 定义一个ArrayStack,表示栈
*/
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("栈满~");
return;
}
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("栈空~");
return;
}
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}
// 获取栈顶的值
public int peek() {
return stack[top];
}
// 返回运算符的优先级
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 res = 0;// 用于存放计算结果
switch (oper) {
case '+':
res = num1 + num2;
break;
case '-':
res = num2 - num1;
break;
case '*':
res = num1 * num2;
break;
case '/':
res = num2 / num1;
break;
default:
break;
}
return res;
}
}
上一篇: 【数据结构】栈---使用栈实现综合计算器(中缀表达式)
下一篇: 9.栈实现综合计算器(中缀表达式)