java数据结构-栈(实现计算器)-爱代码爱编程
1、通过栈进行实现计算器,扫描数据,符号栈与数字栈
2、面对多位数如何进行实现连续扫描
/*
利用栈实现计算器功能
*/
public class AchieveCalculate {
public static void main(String[] args) {
String expression = "30+2*6-2/1";
StackStruct2 numStack = new StackStruct2(10);// 数字栈
StackStruct2 operStack = new StackStruct2(10);// 符号栈
// 定义相关的变量
int index = 0;// 用于扫描
int num1 = 0;
int num2 = 0;
int oper = 0;
int res = 0;
char ch = ' ';// 将每次扫描得到的char保存到ch
String keepNum = ""; // 用于拼接多位数
// 开始while循环的扫描expression
while (true) {
// 依次得到的每一个字符substring
ch = expression.substring(index, index + 1).charAt(0);
// 判断
// 符号
if (operStack.isOper(ch)) {
//如果是运算符
// 判断符号栈是否为空
if (!operStack.isEmpty2()) {
// 如果符号栈中有操作符,就进行比较,如果当前的操作符的优先级小于或等于栈中的操作符,就需要从数栈中pop出两个数
// 再从符号栈中pop 出一个符号符进行运算,入数栈,然后再将当前的符号符入操作符号栈
if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
// 进行数栈pop两个数
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);
keepNum += ch;
// 如果是最后一位,直接入栈
if (index == expression.length() - 1) {
numStack.push(Integer.parseInt(keepNum));
keepNum = "";
} else {
// 判断下一位如果是数字,就继续扫描,如果是运算符,则直接入栈
if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
// 后一位是符号
numStack.push(Integer.parseInt(keepNum));// 将字符转换为数字
// 清空keepnum
keepNum = "";
}
}
}
// 遍历
index++;
if (index >= expression.length()) {
break;
}
}
// 当表达式扫描完毕,就顺序地从数栈和符号栈中pop出相应的数和符号,并运行
while (true) {
// 如果符号栈为空,则计算到最后的结果,数栈中只剩下一个数字,就是结果
if (operStack.isEmpty2()) {
break;
}
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1, num2, oper);
numStack.push(res);
}
// 将数栈中的最后数,pop出,就是结果
int res2 = numStack.pop();
System.out.printf("表达式%s = %d", expression, res2);
}
}
// 栈的结构
class StackStruct2 {
private int maxSize; // 栈的大小
private int[] stack; // 数组
private int top; // 栈顶指针
// 构造器
public StackStruct2(int maxSize) {
this.top = -1;
this.maxSize = maxSize;
this.stack = new int[maxSize];
for (int i = 0; i < stack.length; i++) {
stack[i] = -1;
}
}
// 判断栈是否为空
public boolean isEmpty2() {
return top == -1;
}
public boolean isEmpty() {
boolean indentify = true;
for (int i = 0; i < stack.length; i++) {
if (stack[i] != -1) {
indentify = false;
break;
}
}
return indentify;
}
// 判断栈是否为满
public boolean isFull2() {
return top == stack.length - 1;
}
public boolean isFull() {
boolean indentify = true;
for (int i = 0; i < stack.length; i++) {
if (stack[i] == -1) {
indentify = false;
break;
}
}
return indentify;
}
// 定义入栈方法
public void push(int n) {
if (isFull()) {
throw new RuntimeException("栈已满!");
// System.out.println("栈已满!");
// return;
}
stack[++top] = n;
// System.out.println("入栈: " + n);
}
// 定义出栈方法
public int pop() {
if (isEmpty()) {
throw new RuntimeException("栈为空!");
// System.out.println("栈为空!");
// return;
}
int value = stack[top];
stack[top] = -1;
top--;
return value;
}
// 增加一个方法,可以返回当前栈顶的值,但是不是真正的pop
public int peek() {
int value = stack[top];
return value;
}
// 修改栈内第一次存入的元素
public void upDate(int value, int data) {
if (data == -1) {
System.out.println("修改的数据不合法");
return;
}
for (int i = 0; i < stack.length; i++) {
if (value == stack[i]) {
stack[i] = data;
System.out.println("修改完成!");
break;
} else if (i == stack.length - 1) {
System.out.println("对于原始数据:" + value + ",无法在栈中找到相应的元素进行修改");
}
}
}
// 查看栈内元素
public void show() {
if (isEmpty()) {
throw new RuntimeException("栈为空");
// System.out.println("栈为空");
// return;
}
int num = 0;
System.out.println("序号" + ":" + "值");
for (int i = 0; i < stack.length; i++) {
// 满栈的情况
if (i == stack.length - 1) {
num = i;
break;
} else if (stack[i + 1] == -1) {
num = i;
break;
}
}
for (int j = num; j >= 0; j--) {
System.out.println(j + " : " + stack[j]);
}
}
// 返回运算符的优先及,由程序员来确定,优先级使用数字进行表示
// 数字越大,则优先级就越高
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;
}
return res;
}
}