栈实现中缀表达式
1.创建两个栈，一个用来存储数字一个用来存储操作符号
2.判断每一个字符是数字还是操作符
3.如果是数字，直接存入数栈中
4.如果是符号，看符号栈是否为空，如果为空直接存入
5.如果符号栈不为空，从符号栈中取出一个数据与当前符号比较，如果当前操作符优先级高于栈取出的，直接存入，否则从数栈中弹出两个数据与当前符号进行运算，把得到的结果存入数栈中
6.在判断两位数的时候，我们扫描的时候需要看看下一位是否也是数字，不能拿第一个数字的存入栈中，如果下一位不是数字直接存入，如果下一位是数字接着扫描直到不是，然后拼接字符串，再存入栈中
下面是具体实现：
public static int calculator(String str)
{
Arraystack2 numStack = new Arraystack2(10);
Arraystack2 operStack = new Arraystack2(10);
//定义需要的相关变量
int index = 0;//用于扫描
int num1 = 0;
int num2 = 0;
int oper = 0;
int res = 0;
char ch = ' '; //将每次扫描得到char保存到ch
String keepNum = ""; //用于拼接 多位数
//开始while循环的扫描
while(true) {
//依次得到每一个字符
ch = str.substring(index, index+1).charAt(0);
//判断ch是什么，然后做相应的处理
if(operStack.isOper(ch)) {//如果是运算符
//判断当前的符号栈是否为空
if(!operStack.isEmpty()) {
//如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符,就需要从数栈中pop出两个数,
//在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈
if(operStack.priority(ch) <= operStack.priority(operStack.peek())) {
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1, num2, oper);
//把运算的结果如数栈
numStack.push(res);
//然后将当前的操作符入符号栈
operStack.push(ch);
} else {
//如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈.
operStack.push(ch);
}
}else {
//如果为空直接入符号栈..
operStack.push(ch); // 1 + 3
}
} else { //如果是数，则直接入数栈
keepNum += ch;
if (index == str.length() - 1) {
numStack.push(Integer.parseInt(keepNum));
}else{
//判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈
//注意是看后一位，不是index++
if (operStack.isOper(str.substring(index+1,index+2).charAt(0))) {
numStack.push(Integer.parseInt(keepNum));
keepNum = "";
}
}
}
index++;
if (index >= str.length()) {
break;
}
}
//当表达式扫描完毕，就顺序的从 数栈和符号栈中pop出相应的数和符号，并运行.
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 res2 = numStack.pop();
return res2;
}
自定义栈：
class Arraystack2 {
//栈的大小
private int maxsize;
//模拟栈的数组
private int [] arr;
//指向栈底的指针
private int top=-1;
//初始化
public Arraystack2(int maxsize)
{
this.maxsize=maxsize;
arr=new int[this.maxsize];
}
//判断栈是否满
public boolean isfull()
{
return top==maxsize-1;
}
//判断栈是否为空
public boolean isEmpty()
{
return top==-1;
}
public int peek() {
return arr[top];
}
//入栈
public void push(int a)
{
if (isfull())
{
throw new RuntimeException("栈已经满");
}
top++;
arr[top]=a;
}
//出栈
public int pop()
{
if (isEmpty())
{
throw new RuntimeException("栈位空");
}
int value=arr[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, arr[i]);
}
}
//返回运算符的优先级，优先级是程序员来确定, 优先级使用数字表示
//数字越大，则优先级就越高.
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 == '/';
}
//计算方法
public int cal(int num1, int num2, int oper) {
int res = 0; // res 用于存放计算的结果
switch (oper) {
case '+':
res = num1 + num2;
break;
case '-':
res = num2 - num1;// 注意顺序
break;
case '*':
res = num1 * num2;
break;
case '/':
res = num2 / num1;
break;
default:
break;
}
return res;
}
}