- 首先明确要使用的数据结构，本文采用栈来实现。
- 为了分别操作数字和运算符，采用双栈，一个数值栈和一个运算符栈
- 根据栈顶运算符和待入栈运算符的优先级的判断，产生中间结果，而中间结果作为最终结果的一部分需要再次入栈
- 栈顶运算符优先级大于等于待入栈运算符，则需要计算中间结果
- 栈顶运算符优先级小于待入栈运算符，则直接入栈
public class ArrayStack {
private int maxSize;
private int[] stack;
private int top;
public ArrayStack() {
}
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
this.stack = new int[this.maxSize];
this.top = -1;
}
public boolean isFull() {
return this.top == this.maxSize - 1;
}
public boolean isEmpty() {
return this.top == -1;
}
public void push(int data) {
if (this.isFull()) {
System.out.println("栈满");
return;
}
this.stack[++this.top] = data;
}
public int pop() {
if (this.isEmpty()) {
throw new RuntimeException("栈空");
}
return this.stack[this.top--];
}
//判断栈顶运算符和待入栈运算符的优先级，需要取得栈顶元素
public int getTop() {
return this.stack[this.top];
}
}
public static boolean isSymbol(int value) {
return (value == '+') || (value == '-') || (value == '*') || (value == '/');
}
//判断扫描到的字符是否为运算符，注意：字符类型（不是字符串）在和数值类型进行判等时，会参照ASCII码表
/*验证如下：
char ch = 'A';
int num = ch;
System.out.println(num);//65
System.out.println(num == ch);//true
*/
//定义优先级：+、-的优先级为0，*、/的优先级为1
public static int priority(int value) {
if ((value == '+') || (value == '-')) {
return 0;
} else {
return 1;
}
}
/**
* 3 + 5，其中3为左操作数，5为右操作数
* @param left 左操作数
* @param right 右操作数
* @param symbol 运算符
* @return 运算结果
*/
public static int cal(int left, int right, int symbol) {
int res = 0;
switch (symbol) {
case '*':
res = left * right;
break;
case '/':
res = left / right;
break;
case '+':
res = left + right;
break;
case '-':
res = left - right;
break;
default:
break;
}
return res;
}
扫描表达式字符串，判断扫描到的字符串为符号还是数字
- 如果为数字，则直接入数栈
- 如果为符号，继续判断符号栈是否为空
- 如果符号栈为空，即没有可比较的栈顶运算符，则扫描到的符号直接入栈
- 如果符号栈不为空，继续判断栈顶运算符优先级和所扫描到运算符的优先级
- 栈顶运算符优先级小于等于所扫描运算符，数栈弹出两数，弹出符号栈栈顶运算符，计算中间结果并压入数栈，所扫描运算符入符号栈
- 否则，所扫描运算符直接入符号栈
public static void main(String[] args) {
ArrayStack numStack = new ArrayStack(20);
ArrayStack symbolStack = new ArrayStack(20);
String expression = "9+3*3-7";
int index = 0;//扫描表达式的指针
int leftNum = 0;
int rightNum = 0;
int symbol = 0;//记录出栈运算符
int result = 0;
char ch = ' ';//记录每次扫描到的运算符
//扫描表达式字符串
while (index < expression.length()) {
ch = expression.charAt(index);
index++;
if (isSymbol(ch)) {
if (!symbolStack.isEmpty()) {
if (priority(ch) <= priority(symbolStack.getTop())) {
rightNum = numStack.pop();//从数栈弹出的第一个数为右操作数
leftNum = numStack.pop();//从数栈弹出的第二个数为右操作数
symbol = symbolStack.pop();
result = cal(leftNum, rightNum, symbol);
//中间结果入数栈，扫描到的运算符入符号栈
numStack.push(result);
symbolStack.push(ch);
} else {
symbolStack.push(ch);
}
} else {
symbolStack.push(ch);
}
} else {
numStack.push(ch - 48); // '1' -> 1 (字符串形式的数字转化为真正的数值)
}
}
//表达式扫描完毕，若符号栈还剩下运算符，则继续弹出参与计算，直到为空。
while (!symbolStack.isEmpty()) {
rightNum = numStack.pop();
leftNum = numStack.pop();
symbol = symbolStack.pop();
result = cal(leftNum, rightNum, symbol);
numStack.push(result);
}
//此时数栈剩下的最后一个数字就是最终结果
System.out.println(expression + " 的结果为：" + numStack.pop());
}
String expression = “9+3*3-7”;
如果表达式数字都在10以内，结果不会出现问题
String expression = “90+3*3-7”;
但是表达式数字出现多位数时，结果并不正确
由于在扫描表达式字符串的时候，一次只能扫描一个字符。
实现一中，当扫描到一个数字我们便直接入数栈，这显然是不合理的。例如"245"，扫描到’2’时，我们仅仅是将数值2入栈。
通过原因分析，我们了解到当扫描到一个数字的时候，并不能马上就入栈，而需要继续判断下一个扫描位置是否也为数字。
若下一个扫描位置也为数字，还需要对下下个扫描位置进行判断，进入loop，直到扫描到符号。
那我们就知道，数字字符的宽度已被我们扫描完毕，可以进行入栈操作。
public static void main(String[] args) {
ArrayStack numStack = new ArrayStack(20);
ArrayStack symbolStack = new ArrayStack(20);
String expression = "90+3*3-7";
int index = 0;
int leftNum = 0;
int rightNum = 0;
int symbol = 0;
int result = 0;
char ch = ' ';
String number = "";//用于拼接数字字符
while (index < expression.length()) {
ch = expression.charAt(index);
index++;
if (isSymbol(ch)) {
if (!symbolStack.isEmpty()) {
if (priority(ch) <= priority(symbolStack.getTop())) {
rightNum = numStack.pop();
leftNum = numStack.pop();
symbol = symbolStack.pop();
result = cal(leftNum, rightNum, symbol);
numStack.push(result);
symbolStack.push(ch);
} else {
symbolStack.push(ch);
}
} else {
symbolStack.push(ch);
}
} else {
//拼接当前所扫描的数字字符
number += ch;
//逻辑与顺序不可以交换，因为扫描到最后一个数字字符时，表达式已经到头了
while (index < expression.length() && !isSymbol(expression.charAt(index))) {
//拼接后续所扫描到的数字字符
number += expression.charAt(index);
index++;
}
//将数字字符串转化为数值类型的数字
numStack.push(Integer.parseInt(number));
//注意清空每一轮拼接的数字字符串，否则下一轮会包含上一轮拼接的数字字符
number = "";
}
}
while (!symbolStack.isEmpty()) {
rightNum = numStack.pop();
leftNum = numStack.pop();
symbol = symbolStack.pop();
result = cal(leftNum, rightNum, symbol);
numStack.push(result);
}
System.out.println(expression + " 的结果为：" + numStack.pop());
}
String expression = “315+20*3-10”;
