1、思路分析
使用栈完成计算一个表达式的结果 7*2+1-3
使用栈完成表达式计算的思路
1、 使用一个index值（索引）来遍历我们的表达式；
2、 如果发现是一个数字，入数栈；
3、 如果发现是符号，分以下情况；
1、 如果发现符号栈为空，直接入栈；
2、 符号栈内有操作符，比较当前操作符的优先级；
当前操作符优先级小于或等于栈中的操作符，从数栈中 pop 出两个数，符号栈 pop 出一个符号，进行运算，得到结果入数栈，当前的操作符入符号栈
当前操作符优先级大于栈中的操作符，直接入符号栈
4、 表达式扫描完毕后，顺序的从数栈和符号栈中pop出相应的数和符号，并运行；
5、 最后在数栈中只有一个数字，就是我们的结果；
2、1 - 10 以内表达式计算
2.1 栈功能实现
class ArrayStack{
public int maxSize; // 栈的大小
public int[] stack; // 栈
public int top = -1; // 栈顶
// 构造
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int[maxSize];
}
// 判断栈是否为空
public boolean isEmpty(){
return top == -1;
}
// 判断栈是否满
public boolean isFull(){
return top == maxSize - 1;
}
// 入栈 push
public void push(int value){
if(isFull()) {
System.out.println("栈已满，无法进行入栈操作");
return;
}
top ++;
stack[top] = value;
}
// 出栈 pop
public int pop(){
if (isEmpty()) {
throw new RuntimeException("栈内没有数据");
}
int value = stack[top];
top --;
return value;
}
// 栈顶数据，不出栈
public int peek() {
return stack[top];
}
// 遍历，从栈顶开始展示数据
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 priority(int oper) {
if (oper == '*' || oper == '/') {
return 1;
} else if(oper == '+' || oper == '-') {
return 0;
} else {
return -1;
}
}
// 判断是否为加减乘除运算符
public boolean isOper(char value) {
return value == '+' || value == '-' || value == '*' || value == '/';
}
// 计算方法
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;
default:
break;
}
return result;
}
}
2.2 表达式计算
public class ArrayStackDemo {
public static void main(String[] args) {
String expression = "2*5-8/2"; // 1 - 10 以内进行计算
// 创建数栈和符号栈
ArrayStack numStack = new ArrayStack(10);
ArrayStack operStack = new ArrayStack(10);
int index = 0; // 当前字符下标
int num1 = 0;
int num2 = 0;
int oper = 0;
int result = 0;
char ch = ' '; // 每次扫描结果保存到 ch 中
while (true) {
// 截取字符
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 {
// 因为是个位数，只有一个数字。判断为数字，直接入数栈
numStack.push(ch - 48);
}
// 判断是否扫描到 expression 最后
index ++;
if (index >= expression.length()) {
break;
}
}
numStack.list();
operStack.list();
// 顺序从符号栈中取出相应的数和符号进行计算
while(true) {
// 符号栈为空，则计算到最后的结果，数栈中剩余 1 个数值
if (operStack.isEmpty()) {
break;
}
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
result = numStack.cal(num1, num2, oper);
numStack.push(result);
}
System.out.println("数栈内最后的数为：" + numStack.pop());
}
}
3、多位数进行计算
3.1 栈实现
class ArrayStack{
public int maxSize; // 栈的大小
public int[] stack; // 栈
public int top = -1; // 栈顶
// 构造
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int[maxSize];
}
// 判断栈是否为空
public boolean isEmpty(){
return top == -1;
}
// 判断栈是否满
public boolean isFull(){
return top == maxSize - 1;
}
// 入栈 push
public void push(int value){
if(isFull()) {
System.out.println("栈已满，无法进行入栈操作");
return;
}
top ++;
stack[top] = value;
}
// 出栈 pop
public int pop(){
if (isEmpty()) {
throw new RuntimeException("栈内没有数据");
}
int value = stack[top];
top --;
return value;
}
// 栈顶数据，不出栈
public int peek() {
return stack[top];
}
// 遍历，从栈顶开始展示数据
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 priority(int oper) {
if (oper == '*' || oper == '/') {
return 1;
} else if(oper == '+' || oper == '-') {
return 0;
} else {
return -1;
}
}
// 判断是否为加减乘除运算符
public boolean isOper(char value) {
return value == '+' || value == '-' || value == '*' || value == '/';
}
// 计算方法
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;
default:
break;
}
return result;
}
}
3.2 多位数表达式计算
public class ArrayStackDemo {
public static void main(String[] args) {
String expression = "2*12-8+4"; // 1 - 10 以内进行计算
// 创建数栈和符号栈
ArrayStack numStack = new ArrayStack(10);
ArrayStack operStack = new ArrayStack(10);
int index = 0; // 当前字符下标
int num1 = 0;
int num2 = 0;
int oper = 0;
int result = 0;
char ch = ' '; // 每次扫描结果保存到 ch 中
String keepNum = ""; // 多位数拼接字符
while (true) {
// 截取字符
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 {
// 判断为数字，直接入数栈
// 处理多位数时，在入数栈时，需要向 expression 表达式后一位再看一位
keepNum += ch;
// 如果 index 指向字符串最后一位，直接入数栈
if (index == expression.length() - 1) {
numStack.push(Integer.valueOf(keepNum));
} else {
// 判断后一位是不是数字，如果是数字，继续扫描
if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
// 后一位是运算符，入栈
numStack.push(Integer.valueOf(keepNum));
keepNum = "";
}
}
}
// 判断是否扫描到 expression 最后
index ++;
if (index >= expression.length()) {
break;
}
}
numStack.list();
operStack.list();
// 顺序从符号栈中取出相应的数和符号进行计算
while(true) {
// 符号栈为空，则计算到最后的结果，数栈中剩余 1 个数值
if (operStack.isEmpty()) {
break;
}
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
result = numStack.cal(num1, num2, oper);
numStack.push(result);
}
System.out.println("数栈内最后的数为：" + numStack.pop());
}
}