那，在上一篇呢，已经写好了如何去实现一个栈了。
在最开始我就说过，栈的实现很简单，但用栈来解决一些实际问题，可能会有点难度。
今天这一篇就是用栈这个数据结构，来解决中缀表达式的计算。
也就是数学表达式的计算。
题目也很简单：
假如有个字符串表达式（“5+2*5-4/1”），用栈来计算这个表达式的值。
OKK，现在我们来分析一下怎么来做。然后再用代码实现。
那，这是我整理好的思路，似乎第一眼看到后，很懵逼。
没有关系，我们用一个例子来分析一下，瞬间就会明了。
就用上面我提到过的表达式（5+2*5-4/1）。
我们按步骤来，遍历字符串，然后看每个字符是什么。
第一个是5，直接入数栈。
第二个是+，由于符号栈为空，就直接入符号栈。
第三个是2，直接入数栈。
然后第四个是*，由于×优先级大约+，所以直接入符号栈。
第五个是5，直接入数栈。
然后！！第6个是-，由于-的优先级要小于*，所以此时要把符号栈的栈顶元素弹出。
然后再从数栈弹出两个数，进行运算。
把这个结果入数栈，然后再把-入符号栈！！
然后4直接入数栈。
/的优先级要大于-，直接入符号栈。
1直接入数栈。
OK，这样就将整个字符串遍历完了。
最后一步，把栈中的元素成对pop出就好了。
第一次pop，数栈pop两个，符号栈pop一个。
计算结果入数栈。
然后继续。。
计算结果入数栈。
然后继续。
计算结果入数栈，此时数栈只有一个元素，符号栈为空，OK，那么这个数就是最后的答案！
OK，关于计算中缀表达式的思路我已经全缕清了，那我们就在上次写的栈的基础上，把这个计算中缀表达式的代码实现出来。
由于我们要判断运算符的优先级，但是JAVA有不会自动判断字符的优先级，所以这个优先级要我们自己写出来：
public static int priority(int oper){
if(oper == '+'||oper == '-'){
return 1;
}
else if (oper=='*'||oper == '/'){
return 2;
}
else{
throw new RuntimeException("please enter a right oper");
}
}
然后我还要有一个计算的方法，用来计算pop出的两个数和一个运算符。
public static int add(int num1,int num2,int oper){
if(oper == '+'){
return num1+num2;
}else if(oper == '-'){
return num1-num2;
}else if(oper == '*'){
return num1*num2;
}else if(oper == '/'){
return num1/num2;
}else{
throw new RuntimeException("please enter a right oper");
}
}
OK，有了这两个方法，我们就可以写如何计算中缀表达式的方法了。
首先我么那肯定要有两个栈（一个数栈，一个符号栈）
然后还要吧字符串转换成字符数组
String str = "5+2*5-4/1";
ArrayStack numStack = new ArrayStack(20);
ArrayStack operStack = new ArrayStack(20);
char nums[] = str.toCharArray();
然后上面说的步骤我们直接用代码实现就好：
判断是数字还是运算符，还有优先级。
for (int i=0;i<nums.length;i++){
if(nums[i] == '+'||nums[i] == '-'|| nums[i] == '*' || nums[i] == '/'){
if(operStack.isEmpty()){
operStack.push(nums[i]);
}
else{
if(priority(nums[i])<=priority(operStack.look())){
int nu1 = numStack.pop();
int nu2 = numStack.pop();
int oper2 = operStack.pop();
numStack.push(add(nu2,nu1,oper2));
operStack.push(nums[i]);
}
else{
operStack.push(nums[i]);
}
}
}else{
nums[i]= (char) (nums[i]-48);
numStack.push(nums[i]);
}
}
最后字符串遍历完之后，我们用一个while循环把里面的都pop出来计算：
while (!operStack.isEmpty()){
int nu1 = numStack.pop();
int nu2 = numStack.pop();
int oper2 = operStack.pop();
numStack.push(add(nu2,nu1,oper2));
}
哎，这就没有问题了呀。
所以关于中缀表达式的计算，分析，代码实现也就全做完了。
最后再把整个代码献上。（因为一遍下来的，可能会有点小瑕疵）。
package Stack;
public class Calculator {
public static void main(String[] args) {
System.out.println("结果为：");
System.out.println(count());
}
public static int priority(int oper){
if(oper == '+'||oper == '-'){
return 1;
}
else if (oper=='*'||oper == '/'){
return 2;
}
else{
throw new RuntimeException("please enter a right oper");
}
}
public static int add(int num1,int num2,int oper){
if(oper == '+'){
return num1+num2;
}else if(oper == '-'){
return num1-num2;
}else if(oper == '*'){
return num1*num2;
}else if(oper == '/'){
return num1/num2;
}else{
throw new RuntimeException("please enter a right oper");
}
}
public static int count(){
String str = "5+2*5-4/1";
ArrayStack numStack = new ArrayStack(20);
ArrayStack operStack = new ArrayStack(20);
char nums[] = str.toCharArray();
for (int i=0;i<nums.length;i++){
if(nums[i] == '+'||nums[i] == '-'|| nums[i] == '*' || nums[i] == '/'){
if(operStack.isEmpty()){
operStack.push(nums[i]);
}
else{
if(priority(nums[i])<=priority(operStack.look())){
int nu1 = numStack.pop();
int nu2 = numStack.pop();
int oper2 = operStack.pop();
numStack.push(add(nu2,nu1,oper2));
operStack.push(nums[i]);
}
else{
operStack.push(nums[i]);
}
}
}else{
nums[i]= (char) (nums[i]-48);
numStack.push(nums[i]);
}
}
while (!operStack.isEmpty()){
int nu1 = numStack.pop();
int nu2 = numStack.pop();
int oper2 = operStack.pop();
numStack.push(add(nu2,nu1,oper2));
}
return numStack.look();
}
}
哦对，这里面我在栈里面定义了一个look方法用来查看栈顶元素（但是不出栈）。
OK，END。