原理
两个栈：1个操作数栈（存储数字），1个运算符栈（存储运算符+-*/）
运算符优先级比较：
- 运算符栈空，入栈，i++
- 等待入栈的运算符优先级高于栈顶运算符，入栈，i++
- 等待入栈的运算符优先级等于栈顶运算符，出栈，运算结果入栈
- 等待入栈的运算符优先级低于栈顶运算符，出栈，运算结果入栈
运算方式：运算结果=后栈操作数 出栈运算符 先出栈操作数
代码
package xcrj.stack;
import java.util.Scanner;
/**
* 自然数0~9的加减乘除运算，不包括括号，a?b的运算结果要为整数
*/
public class SimpleInfixExpressionEvaluation {
private static class StackOperator {
private char[] operators;
private int stackSize;
// 初始栈顶
private int top = -1;
StackOperator(int stackSize) {
this.stackSize = stackSize;
this.operators = new char[stackSize];
}
public boolean isFull() {
return top == this.stackSize - 1;
}
public boolean isEmpty() {
return top == -1;
}
/**
* 入栈
*/
public void push(char operator) {
if (this.isFull()) {
System.out.println("栈满");
return;
}
this.top++;
this.operators[this.top] = operator;
}
/**
* 出栈
*/
public char pop() {
if (this.isEmpty()) {
throw new RuntimeException("栈空");
}
char value = this.operators[this.top];
this.top--;
return value;
}
/**
* 获取栈顶元素
*/
public char peak() {
if (this.isEmpty()) {
throw new RuntimeException("栈空");
}
return this.operators[this.top];
}
}
private static class StackOperand {
private int[] operands;
private int stackSize;
// 栈顶
private int top = -1;
StackOperand(int stackSize) {
this.stackSize = stackSize;
this.operands = new int[stackSize];
}
public boolean isFull() {
return top == this.stackSize - 1;
}
public boolean isEmpty() {
return top == -1;
}
/**
* 入栈
*/
public void push(int operand) {
if (this.isFull()) {
System.out.println("栈满");
return;
}
this.top++;
this.operands[this.top] = operand;
}
/**
* 出栈
*/
public int pop() {
if (this.isEmpty()) {
throw new RuntimeException("栈空");
}
int value = this.operands[this.top];
this.top--;
return value;
}
/**
* 获取栈顶元素
*/
public int peak() {
if (this.isEmpty()) {
throw new RuntimeException("栈空");
}
return this.operands[this.top];
}
}
public static boolean isOperator(char v) {
if ('+' == v) {
return true;
}
if ('-' == v) {
return true;
}
if ('*' == v) {
return true;
}
if ('/' == v) {
return true;
}
return false;
}
public static boolean isOperand(char v) {
// ASCII判断
return v >= 48 && v <= 57;
}
/**
* 获得运算符的优先级
*/
public static int priority(char operator) {
switch (operator) {
case '-':
return 1;
case '+':
return 2;
case '/':
return 3;
case '*':
return 4;
}
throw new RuntimeException("非法字符");
}
public static int compute(int a, char operator, int b) {
switch (operator) {
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
}
throw new RuntimeException("非法运算符");
}
public static int infixExpressionEvaluation(char[] values) {
int len = values.length;
StackOperator stackOperator = new StackOperator(len);
StackOperand stackOperand = new StackOperand(len);
for (int i = 0; i < len; ) {
char v = values[i];
// +-*/
if (isOperator(v)) {
// 栈空入栈
if (stackOperator.isEmpty()) {
stackOperator.push(v);
i++;
continue;
}
// 优先级高入栈
if (priority(v) > priority(stackOperator.peak())) {
stackOperator.push(v);
i++;
continue;
}
// 优先级相等出栈
if (priority(v) == priority(stackOperator.peak())) {
int b = stackOperand.pop();
char o = stackOperator.pop();
int a = stackOperand.pop();
int result = compute(a, o, b);
stackOperand.push(result);
continue;
}
// 优先级低出栈
if (priority(v) < priority(stackOperator.peak())) {
int b = stackOperand.pop();
char o = stackOperator.pop();
int a = stackOperand.pop();
int result = compute(a, o, b);
stackOperand.push(result);
continue;
}
}
// 0~9
if (isOperand(v)) {
// -48：0~9的自然数的ASCII码
stackOperand.push(v - 48);
i++;
}
}
// 计算
while (!stackOperator.isEmpty()) {
// 输出结果
int b = stackOperand.pop();
// 出栈1个操作符
char o = stackOperator.pop();
// 出栈1个操作数
int a = stackOperand.pop();
// 返回计算结果
int result = compute(a, o, b);
stackOperand.push(result);
}
// 获得结果
int result = stackOperand.pop();
// 判断栈空
if (!stackOperand.isEmpty()) {
throw new RuntimeException("非法表达式");
}
return result;
}
public static void main(String[] args) {
// 数组录入
System.out.println("请输入1个表达式(自然数0~9的加减乘除运算，不包括括号，a?b的运算结果要为整数): ");
System.out.println("示例：3*4+2/2-5");
Scanner s = new Scanner(System.in);
String inputStr = s.nextLine();
System.out.println("输入为：" + inputStr);
char[] values = inputStr.toCharArray();
int result = infixExpressionEvaluation(values);
System.out.println("中缀表达式求值结果：" + result);
}
}
