1.思路
4+3*2-1 2.具体实现
关于优先级的判断
若优先级大于前一个符号，则继续进行入栈操作
4.当表达式遍历完后，则两个数字、一个符号依次出栈，进行操作，最后栈中剩的最后一个数为结果
3.代码实现
package test;
/**
* @author WuChenGuang
*/
public class Test01 {
public static void main(String[] args) {
String str = "4+3*2-1";
/*
1.需要遍历字符串，获取每一个字符
2.判断当前字符是一个运算符还是一个数字
3.把数字存放在数字栈中，把运算符放在运算符栈
4.运算符栈：
如果是一个空栈，那么直接运算符入栈，如果运算符栈中已经了其他运算符，
就需要先对比运算符优先级，新进来的运算符如果小于等于原栈中运算符，那么需要把原运算符弹栈
，数字栈中数字进行弹栈，进行运算，运算后的结果重新放入数字栈中，新运算符入栈。
如果新运算符优先级大于原符号栈中运算符，那么新的符号直接入栈
*/
// 数字栈
ArrayStack numStack = new ArrayStack(10);
// 符号栈
ArrayStack symbolStack = new ArrayStack(10);
// 获取字符串长度
int temp1;
int temp2;
int symbolChar;
int result;
int length = str.length();
StringBuilder values = new StringBuilder();
for (int i = 0; i < length; i++) {
char c = str.charAt(i);
// 判断是否是一个运算符
if (symbolStack.isOper(c)) {
// 如果不是一个空符号栈
if (!symbolStack.isEmpty()) {
// 比较运算符的优先级
if (symbolStack.priority(c) <= symbolStack.priority(symbolStack.peek())) {
/*
1.去符号栈中获取栈顶的符号
2.去数字栈中获取两个数字
*/
temp1 = numStack.pop();
temp2 = numStack.pop();
symbolChar = symbolStack.pop();
result = numStack.calculate(temp1, temp2, symbolChar);
// 把运算结果再次放入数字栈中
numStack.push(result);
// 把当前符号压入符号栈中
symbolStack.push(c);
} else {
symbolStack.push(c);
}
} else {
// 如果是空符号栈，讲运算符直接压栈
symbolStack.push(c);
}
} else {
// 比如 33+44
values.append(c);
if (i == length - 1) {
numStack.push(Integer.parseInt(values.toString()));
} else {
char data = str.substring(i + 1, i + 2).charAt(0);
if (symbolStack.isOper(data)) {
numStack.push(Integer.parseInt(values.toString()));
values = new StringBuilder();
}
}
}
}
while (!symbolStack.isEmpty()) {
temp1 = numStack.pop();
temp2 = numStack.pop();
symbolChar = symbolStack.pop();
result = numStack.calculate(temp1, temp2, symbolChar);
numStack.push(result);
}
int res = numStack.pop();
System.out.println("4+3*2-1的结果是: " + res);
}
}
package test;
/**
* @author WuChenGuang
*/
public class ArrayStack {
// 栈的大小
private int maxStack;
// 数组用来模拟栈
private int[] stack;
// 表示栈顶所在的位置，默认情况下如果没有数据时，使用-1
private int top = -1;
public ArrayStack(int maxStack) {
this.maxStack = maxStack;
stack = new int[maxStack];
}
/**
* 判断是否已经满栈
*/
public boolean isFull() {
return this.top == this.maxStack - 1;
}
/**
* 判断栈是否是空栈
*/
public boolean isEmpty() {
return this.top == -1;
}
/**
* 压栈
*/
public void push(int val) {
// 判断是否已经栈满
if (isFull()) {
throw new RuntimeException("此栈已满");
}
// System.out.println(val + "入栈了");
top++;
stack[top] = val;
}
/**
* 弹栈
*/
public int pop() {
// 如果栈中是空
if (isEmpty()) {
throw new RuntimeException("空栈，未找到数据");
}
int value = stack[top];
top--;
return value;
}
/**
* 查看栈中所有元素
*/
public void list() {
// 判断是否是空栈
if (isEmpty()) {
throw new RuntimeException("空栈，未找到数据");
}
for (int i = 0; i < stack.length; i++) {
System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}
/**
* 栈中元素存在的个数
*/
public int length() {
return this.top + 1;
}
/**
* 判断是否是一个运算符 + - * /
*/
public boolean isOper(char v) {
return v == '+' || v == '-' || v == '*' || v == '/';
}
/**
* 判断运算符优先级 使用数字表示优先级大小，数字越大的优先级越大
*/
public int priority(int oper) {
if (oper == '*' || oper == '/') {
return 1;
} else if (oper == '+' || oper == '-') {
return 0;
} else {
return -1;
}
}
/**
* 获取栈顶数据
*/
public int peek() {
return this.stack[top];
}
/**
* 获取栈的容量
*/
public int stackLength() {
return this.stack.length;
}
/**
* 计算两个数进行运算后的结果
* 2-3
* 3:num1,2:num2
*/
public int calculate(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;
}
}运行结果：
