-
基本思路:
（1）通过一个index值作为索引（int类型），来遍历多项式；
（2）如果扫描到一个数字，就直接入数栈；
（3）如果扫描到一个符号，就分以下情况：
a、如果当前符号栈为空，就将该符号直接入符号栈；
b、如果符号栈不为空，就要进行优先级的比较：
1、如果 当前扫描到的操作符 的优先级 小于或等于 栈顶的操作符，就要从 数栈 中 pop 出两个数，同时从 符号栈 中 pop 出一个符号，构成运算式进行运算。运算得到的结果 入数栈，然后再将 当前扫描到的操作符 入符号栈
2、如果 当前扫描到的操作符 的优先级 大于 栈顶的操作符，就直接入符号栈。
（4）当多项式扫描完毕时，就依次从 数栈 和 符号栈 中 pop 出相应的数和符号（每一轮pop出 2个数和1个符号 ，组成一个运算式进行运算，将运算结果 压入数栈），循环往复。
（5）最后，符号栈会空，数栈中留下最后一个数，该数即为运算结果。
首先创建一个数组栈，实现基本的操作如下：
// 定义一个ArrayStack 表示栈
class ArrayStackCul {
private int maxSize; // 栈的最大容量
private int[] stack; // 数组模拟栈，数据放在该数组中
private int top = -1;//栈顶指针
// 构造器
public ArrayStackCul(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]);
}
}
}
为了实现多项式运算，还要为该栈功能进行拓展：
（1）为了比较扫描串中 当前扫描的运算符 和 栈顶运算符 的优先级，定义peek()方法，直接返回 栈顶的元素值，但不取出；
（2）比较运算符优先级的前提是定义和返回优先级，故定义priority(char oper)方法，用于返回操作符oper的优先级；
（3）因为多项式中既有操作符又有数字，为了方便区分，定义isOper(char)方法，用于判断该符号是否是操作符；
（4）定义一个cal(int num1, int num2 , char oper)方法，根据oper运算符的不同，实现不同运算式的统一计算。
// 为了实现运算器的功能，需拓展功能：
/*
* 返回运算符的优先级，优先级由程序员来确定，用数字来表示 默认：数字越大，优先级越高
*/
/*
* 为了将扫描串中的运算符与栈顶运算符进行比较 定义一个方法，直接返回栈顶的元素值，但不取出
*/
//该方法用于查看栈顶元素
public int peek() {
return stack[top];
}
// 该方法用于返回元素的优先级
// 在java中int 和 char 是可以比较的
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 == '/';
}// 在当前情景下，不是运算符当然就只能是数字了
//此方法用于计算出栈元素构成运算式的运算结果
// num1比num2先出栈，oper为运算符
public int cal(int num1, int num2, int oper) {
int res = 0;// res用来存放运算的结果
switch (oper) {
case '+':
res = num2 + num1;
break;
case '-':
res = num2 - num1;
break;
case '*':
res = num2 * num1;
break;
case '/':
res = num2 / num1;
break;
default:
System.out.println("符号有误。");
break;
}
return res;
}
最后在main函数中实现开头的思路：（难点）注释详细
package Stack;
public class Calculator {
public static void main(String[] args) {
// 根据前面的思路，完成表达式的运算
String expression = "70+20*6-20/4"; // 如何处理多位数的问题？
// 创建两个栈，一个数栈，一个符号栈
ArrayStackCul numStack = new ArrayStackCul(10);
ArrayStackCul operStack = new ArrayStackCul(10);
// 创建需要的变量
int index = 0;// 用于扫描
char ch = ' ';// 扫描到的结果存储在ch里面，进行下一步的判断
int num1;
int num2;
int oper;// num1为先出栈数据
int res;// 运算结果
String keepNum = "";// 用于处理多位数运算问题（难点），该变量用来存储一个多位数
while (true) {
// 开始扫描
ch = expression.substring(index, index + 1).charAt(0);
// subString指的是取一个子串；charAt(0)表示取子串的第一个字符
if (operStack.isOper(ch)) {// 如果是运算符
if (!operStack.isEmpty()) {
if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
// ① 扫描的当前运算符 < 栈顶运算符 ——> 执行思路1
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1, num2, oper);
// 运算出的结果入栈
numStack.push(res);
// 最后还要将当前优先级小的运算符入栈
operStack.push(ch);
} else {
// ② 当前运算符的优先级大，执行思路2
operStack.push(ch);
}
} else {// 如果当前符号栈为空，则直接入栈
operStack.push(ch);
}
} else {// 如果是数字,直接入数字栈
/*
* // numStack.push(ch);//这样写是错误的，因为我们得到的数字其实是'字符'
* numStack.push(ch - 48);//字符模式的数 与 数字模式的数 ASCII码差了48
*/
// 以上做法无法处理多位数的问题，解决多位数计算问题的思路：
/*
* 1、当处理数时，不能发现是一个数，就直接入栈 2、在处理数字时，需要想expression的表达式的index后再看一位
* 如果是数，就继续扫描；如果是运算符，则将扫描的整体转换成数值后入栈
* 3、因此需要定义一个字符串变量用于拼接（KeepNum）
*/
keepNum += ch;
// 往后试探一位index + 1 ，如果是数字，则继续扫描；如果是运算符，则入栈
// 另外如果ch已经是expression的最后一位，就直接入栈
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置为空
keepNum = "";
}
}
}
// 让index + 1 ， 并判断是否扫描到expression的最后
// index只是扫描的索引，每扫描一个字符就+1，index >= 字符串长度时，表示扫描完
index++;
if (index >= expression.length()) {
break;
}
}
// 表达式扫描完毕后，
// 依次弹出两个栈中的数和符号，依次计算结果，直到符号栈空
while (true) {
// ③ 如果符号栈为空，则计算最后的结果，即数栈中的最后一个数
if (operStack.isEmpty()) {
break;
}
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1, num2, oper);
numStack.push(res);
}
// 将数栈中最后一个数pop出来，就是结果
int result = numStack.pop();
System.out.printf("表达式%s = %d", expression, result);
}
}
}