使用栈实现综合计算器(中缀表达式)
1.栈的实际需求
请输入一个表达式，计算式:[722-5+1-5+3-3] ，计算出结果
计算机底层是如何运算得到结果的？ 注意不是简单的把算式列出运算,因为我们看这个算式 7 * 2 * 2 - 5, 但是计算机怎么理解这个算式的(对计算机而言，它接收到的就是一个字符串)，我们讨论的是这个问题。-> 栈
2.使用栈实现表达式计算的大致思路(详细思路见代码)
（1）创建一个临时变量index索引，来遍历表达式；并创建两个栈空间，一个数栈，一个符号栈。
（2）从前往后遍历字符串，如果是一个数字，就直接入数栈。
（3）如果发现是一个符号，就分为如下情况
（3.1）如果当时符号栈为空就直接入符号栈
（3.2）如果符号栈不为空，就比较当前要入栈的符号与当前栈顶符号做比较；如果要入栈的符号小于等于栈顶符号的优先级，就从数栈中pop出两个数，并且从符号栈中pop出当前栈顶符号，进行运算，并将运算结果重新压入数栈中，然后将当前想要入栈的符号加入符号栈。
（3.3）如果当前的操作符的优先级大于栈顶符号，就直接加入符号栈
（4）当表达式遍历完毕时，就顺序的从数栈和符号栈中pop出相应的数和符号，并运算，之后将结果压入栈中，如此往复，直到符号栈中没有符号为止。
（5）当在数栈中只有一个数字时，就是表达式的结果
3.代码实现
package cn.zzw.algorithm.Stack;
import java.util.Scanner;
public class ArrayStackDemo1 {
public static void main(String[] args) {
//测试表达式的计算结果是否正确
//当然在这里要思考一下如何处理多位数的加减乘除问题
String expression="1000+102*2-6+2*4";
//创建两个栈，一个用来存储数字，一个用来存储符号
ArrayStack1 numStack=new ArrayStack1(15);
ArrayStack1 operStack = new ArrayStack1(15);
//定义需要的相关变量
int index=0;
int num1=0;
int num2=0;
int operator;
int result=0;
//将每次扫描得到的char保存到ch中
char ch=' ';
//用于拼接多位数
String keepNum="";
//使用while循环遍历表达式
while (true)
{
//一次得到expression的每一个字符
ch=expression.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();
operator=operStack.pop();
result=numStack.caluator(num1,num2,operator);
//将运算完的结果重新压入栈中
numStack.push(result);
//然后将当前操作符如符号栈
operStack.push(ch);
}
else
{
//此时是想要入栈的符号比符号栈顶的符号优先级大，就直接入栈
operStack.push(ch);
}
}
else
{
//如果符号栈为空，就直接将其压入栈中
operStack.push(ch);
}
}
//如果是数字，直接入数栈
else
{
//由于有时候是多位数，分析思路如下
//1.当处理多位数时，不能发现一个数就直接入栈
//2.在处理数字时，需要想expression表达式的index后再看一位，如果是数就进行扫描，如果是符号就入栈
//3.需要定义一个字符串变量，用于拼接
keepNum+=ch;
if (index==expression.length()-1)
{
numStack.push(Integer.parseInt(keepNum));
}
else
{
//判断下一个数字是不是数字，如果是就继续扫描，如果是运算符，则入栈
//注意是看后一位，不是index++
if(operStack.isOper(expression.substring(index+1,index+2).charAt(0)))
{
numStack.push(Integer.parseInt(keepNum));
//重要的是要注意把keepNum清空
keepNum="";
}
}
}
//让index++,并判断是否到expression的最后
index++;
if(index>=expression.length())
{
break;
}
}
//当表达式扫描完毕时，则顺序的从数栈和符号栈中弹出相应的数字和符号，并运算，并将运算结果压入栈中
while(true)
{
//如果字符栈中字符为空，说明已经计算到了最后一步
if(operStack.isEmpty())
{
break;
}
num1=numStack.pop();
num2=numStack.pop();
operator=operStack.pop();
result=numStack.caluator(num1,num2,operator);
numStack.push(result);
}
//这时数栈最后一个元素便是最后的结果
int result2=numStack.pop();
System.out.printf("表达式%s=%d",expression,result2);
}
}
class ArrayStack1
{
private int maxSize;
private int[] stack;//使用数组模拟栈
private int top=-1;
//确定当前符号的优先级，优先级用数字表示
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 caluator(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;
}
//增加一个方法，可以返回当前符号栈的栈顶的值，但不是真正的pop
public int peek()
{
return stack[top];
}
//构造器
public ArrayStack1(int maxSize)
{
this.maxSize=maxSize;
stack=new int[this.maxSize];
}
//判断栈满
public boolean isFull()
{
return top==maxSize-1;
}
//判断栈空
public boolean isEmpty()
{
return top==-1;
}
//入栈操作
public void push(int value)
{
if(isFull())
{
System.out.println("栈满，不能再添加元素");
return;
}
top++;
stack[top]=value;
}
//出栈操作
public int pop()
{
if(isEmpty())
{
throw new RuntimeException("栈空");
}
int value=stack[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,stack[i]);
}
}
}
4.测试结果
"C:\Program Files\Java\jdk1.8.0_181\bin\java.exe" "-javaagent:D:\IntelliJ IDEA\IntelliJ IDEA 2019.3.3\lib\idea_rt.jar=21513:D:\IntelliJ IDEA\IntelliJ IDEA 2019.3.3\bin" -Dfile.encoding=UTF-8 -classpath "C:\Program Files\Java\jdk1.8.0_181\jre\lib\charsets.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\deploy.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\access-bridge-64.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\cldrdata.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\dnsns.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\jaccess.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\jfxrt.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\localedata.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\nashorn.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\sunec.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\sunjce_provider.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\sunmscapi.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\sunpkcs11.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\zipfs.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\javaws.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\jce.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\jfr.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\jfxswt.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\jsse.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\management-agent.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\plugin.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\resources.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\rt.jar;C:\Users\1\IdeaProjects\algorithm\out\production\algorithm" cn.zzw.algorithm.Stack.ArrayStackDemo1
表达式1000+102*2-6+2*4=1206
Process finished with exit code 0