目录
- 栈
- Java实现栈
- 栈实现综合计算器
- 1.中缀表达式直接计算
- 2.后缀表达式计算
- 中缀表达式转后缀表达式
栈
栈（stack）又名堆栈，它是一种运算受限的线性表 。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
概念随便一看，反正就是先进后出的一种数据结构，什么是栈这里不做赘述，下面看一下如何在Java中，利用数组实现模拟一个栈。
Java实现栈
可以用数组来简单的模拟出一个栈的结构。
栈一共两个操作，入栈和出栈
我们只需要一个指针指向栈顶即可完成：
1.出栈的时候将栈顶指针指向的数据取出，指针左移一位指向新的栈顶数据
2.入栈的时候将栈顶指针后移一位，新的栈顶数据放入指针所在位置
注意：当然，由于数组存储空间是定长的，需要指定栈的大小，出入栈也需要判断栈空、栈满
用类ArrayStack作为栈对象
1.属性maxSize存放栈的大小，用于判断栈是否满
2.属性stack[]是用于存放栈的数组
3.top指针指向栈顶，初始化指向-1（因为入栈要先后移）
4.方法有——查看栈顶数据、判断栈是否空、判断栈是否满、入栈、出栈、打印栈
代码如下：
class ArrayStack{
/**
* 栈的大小
*/
private int maxSize;
/**
* 数组，模拟栈
*/
private int[] stack;
/**
* top表示栈顶数据所在数组位置的下标,初始化为-1
*/
private int top = -1;
/**
* 构造器，初始化栈
* @param maxSize 栈的大小
*/
public ArrayStack(int maxSize){
this.maxSize = maxSize;
stack = new int[maxSize];
}
/**
* 返回当前栈顶的值，不出栈
* @return 当前栈顶的值
*/
public int topData(){
return stack[top];
}
/**
* 判断栈是否满
*/
public boolean isFull(){
return top==maxSize-1;
}
/**
* 判断栈是否空
*/
public boolean isNull(){
return top==-1;
}
/**
* 入栈
* @param data 入栈的数据
*/
public void push(int data){
//先判断栈是否是满的
if (isFull()){
//如果是满的，打印错误，直接返回
System.out.println("栈已满");
return;
}
//栈没满，入栈
// top++;stack[top]=data;
stack[++top] = data;
}
/**
* 出栈
* @return 返回栈顶数据
*/
public int pop(){
//先判断栈是否为空
if (isNull()){
//如果为空，抛出异常
throw new RuntimeException("栈为空，没有可出栈数据");
}
//不为空执行出栈
return stack[top--];
}
/**
* 显示栈的情况，从栈顶显示到栈底
*/
public void showStack(){
//先判断是否为空栈
if (isNull()){
System.out.println("栈为空，没有数据");
return;
}
//遍历显示栈
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n",i,stack[i]);
}
}
至此，一个简单的栈结构就模拟完成了
那么栈可以用来做什么呢？
进制转换、判断括号是否匹配、算数表达式的计算、中缀表达式转换后缀表达式
本文来实现一个中缀表达式的计算、后缀表达式计算以及中缀表达式转换后缀表达式
栈实现综合计算器
首先分析，表达式由运算数和运算符组成，运算符具有优先级问题，所以在计算一个表达式时，是根据运算符优先级顺序对运算数进行对应运算符的计算
那么首先需要一些工具方法对用于遍历表达式时的判断，和运算表达式时的计算
包括：
1.判断字符是否是一个运算符
2.判断字符是否是括号
3.判断运算符的优先级
4.根据运算符计算两个数据
/**
* 判断char字符是否是一个运算符
* @param operator 要检测是否是运算符的char
* @return 是否为运算符
*/
static boolean isOperator(int operator){
return operator=='+'||operator=='-'||operator=='*'||operator=='/';
}
/**
* 判断char字符是否是括号
*/
static boolean isBracket(int operator){
return operator=='('||operator==')';
}
/**
* 返回运算符优先级（数字大优先级高）
* @param operator 运算符
* @return 表示优先级的int
*/
static int priority(int operator){
if (operator == '+' || operator == '-'){
return 0;
}
if (operator == '*' || operator == '/'){
return 1;
}
return -1;
}
/**
* 根据运算符计算两个数据
* @param num1 数据1
* @param num2 数据2
* @param operator 运算符（+-*除）
* @return 运算结果
*/
static int calculate(int num1,int num2,int operator){
int res = 0;
switch (operator){
case '+':
res = num2 + num1;
break;
case '-':
res = num2 - num1;
break;
case '*':
res = num2 * num1;
break;
case '/':
res = num2 / num1;
break;
default:
break;
}
return res;
}
1.中缀表达式直接计算
这里实现直接计算一个中缀表达式，没有写入对括号的判断，所以只能是计算最简单的加减乘除
具体实现思路，需要两个栈，一个栈放运算数，一个栈放运算符
遍历整个算数表达式的字符串：
会有两种情况，遇到运算符或者遇到运算数
1.如果遇到运算数就加入到数栈中
2.如果是运算符需要循环判断符号栈的情况，如果符号栈不为空且当前运算符优先级小于等于栈顶运算符，就弹出两个运算数一个运算符进行计算，计算结果压入数栈；直到符号栈为空或者当前运算符优先级大于栈顶，就将当前运算符入符号栈
3.算术表达式遍历结束后，继续计算，循环弹出两个数一个符号，计算结果入数栈，直到符号栈为空，此时数栈中剩下一个数字就是表达式的计算结果
/**
* 计算中缀表达式的结果（不能含有括号）
* @param expression 中缀表达式
* @return 结果
*/
static int calculateMid(String expression) {
//数字栈
ArrayStack numStack = new ArrayStack(10);
//运算符栈
ArrayStack operatorStack = new ArrayStack(10);
//遍历字符串进行入栈等运算操作
for (int i = 0; i < expression.length(); i++) {
//遍历到字符串中的一个字符
char ch = expression.charAt(i);
//判断是否为运算符
if (isOperator(ch)) {
//如果是运算符,判断当前符号栈是否为空
//不为空，判断当前符号优先级和栈中符号优先级的关系进行操作
//当前运算符优先级小于等于栈中运算符优先级，从数栈中pop两个数据，运算符栈中pop一个运算符进行计算，计算结果push进数栈，新运算符再次进行优先级判断
while (!operatorStack.isNull() && priority(ch) <= priority(operatorStack.topData())){
int num1 = numStack.pop();
int num2 = numStack.pop();
int operator = operatorStack.pop();
int res = calculate(num1, num2, operator);
numStack.push(res);
}
//直到当前运算符优先级大于栈中运算符优先级或栈为空，再入栈
operatorStack.push(ch);
}else {
//如果不是运算符,判断是否是数字
if (Character.isDigit(ch)) {
//如果是数字，准备记录下这个数字
StringBuilder num = new StringBuilder(String.valueOf(ch));
//找到下一个字符判断，进行拼接操作，直到下一个为运算符或没有下一个字符为止
while (i+1 < expression.length()&&!isOperator(expression.charAt(i+1))) {
//如果还是数字，先将数字拼接,再i++
num.append(expression.charAt(i+1));
i++;
}
numStack.push(Integer.parseInt(num.toString()));
}else {
//如果不是数字（到这里就既不是数字也不是运算符）报错表达式有误
throw new RuntimeException("运算表达式有误,不支持的符号:[ "+ch+" ]");
}
}
}
//遍历结束后将栈中继续计算直到数栈中只有一个数字，就是结果
while (!operatorStack.isNull()){
int num1 = numStack.pop();
int num2 = numStack.pop();
int operator = operatorStack.pop();
int res = calculate(num1, num2, operator);
numStack.push(res);
}
return numStack.pop();
}
2.后缀表达式计算
后缀表达式是也称逆波兰表达式，是一种计算机更好处理的表达式结构
因为后缀表达式相当于按照优先级、括号等，排好了计算顺序，计算机只需要顺序向后加载计算即可
用到一个数栈就够了，只需要遍历表达式，遇到数字直接入栈，遇到符号直接出栈两个数字进行运算，将结果再入栈，直到表达式遍历结束，栈中就剩下一个数字就是计算结果
代码如下：
这里将表达式格式限制为每个不同元素用空格隔开，便不需要加载操作数时判断多位数了
/**
* 计算后缀表达式
* @param expression 后缀表达式
* @return 计算结果
*/
static int calculateSuf(String expression){
//1.将后缀表达式拆开放入集合
String[] expressionList = expression.split(" ");
//2.创建数栈
ArrayStack numStack = new ArrayStack(10);
for (String s : expressionList) {
//判断是否是符号
if (isOperator(s.charAt(0))) {
//是符号就出栈两个数据进行计算
int num1 = numStack.pop();
int num2 = numStack.pop();
int res = calculate(num1, num2, s.charAt(0));
//计算结果入栈
numStack.push(res);
}else {
//不是符号转换为数字入栈即可
int num;
try {
num = Integer.parseInt(s);
}catch (NumberFormatException e){
throw new RuntimeException("错误的表达式：[ "+s+" ]");
}
numStack.push(num);
}
}
return numStack.pop();
}
中缀表达式转后缀表达式
中缀表达式就是生活中使用的算数表达式
比如一个中缀表达式：1+((2+3)*4)-5
转换为后缀表达式为：1 2 3 + 4 * + 5 –
目前，如果要我自己去转换，一般采用树来辅助，更好记忆和理解，将中缀表达式转换成树形结构，再后序遍历这个树就能得到后缀表达式
这个转换过程，用算法来完成，是稍有些复杂的，转换算法也是前人长时间的智慧结晶，没有看到过转换方法之前，自己想不到怎么转换还算蛮正常的，重点体会一下这个思路就好，其实整个思路也是根据之前计算中缀表达式得来
转换算法思路：
1.初始化两个栈，一个是符号栈s1，一个是中间结果栈s2
2.从左到右扫描中缀表达式
3.遇到操作数直接入栈s2
4.遇到运算符还是循环判断，当运算符栈不为空且当前运算符优先级不大于栈顶运算符时，就弹出一个运算符压入中间结果栈，直到栈为空或当前运算符优先级大于栈顶运算符优先级（这里判断优先级，会出现左括号，左括号当做最低优先级，也就是遇到左括号就直接运算符入栈即可）
5.遇到括号时，如果是左括号，直接入栈s1；如果是右括号，依次弹出s1中的运算符压入s2，直到遇见左括号为止，此时将一对括号丢弃
6.直到整个表达式遍历结束，再将s1中剩余的运算符依次弹出压入s2
此时s2栈弹出顺序的逆序就是后缀表达式
代码如下：
static String infixToSuffix(String infix){
//运算符栈
ArrayStack operatorStack = new ArrayStack(20);
//结果栈
ArrayStack resStack = new ArrayStack(20);
//遍历扫描中缀表达式
for (int i = 0; i < infix.length(); i++) {
//遍历到的一个字符
char ch = infix.charAt(i);
//判断是否为运算符
if (isOperator(ch)){
//循环判断如果运算符栈不为空且当前运算符优先级不大于栈顶运算符
while (!operatorStack.isNull() && priority(ch) <= priority(operatorStack.topData())){
//弹出运算符栈压入结果栈
resStack.push(operatorStack.pop());
}
//当前运算符入运算符栈
operatorStack.push(ch);
}
//如果不是运算符再判断是否是运算数，是就直接压入结果栈
else if (Character.isDigit(ch)){
//如果是数字，记录下这个数字压入结果栈
StringBuilder num = new StringBuilder(String.valueOf(ch));
//找到下一个字符判断，进行拼接操作，直到下一个为运算符或没有下一个字符为止
while (i+1 < infix.length()&&Character.isDigit(infix.charAt(i+1))) {
//如果还是数字，先将数字拼接,再i++
num.append(infix.charAt(i+1));
i++;
}
resStack.push(Integer.parseInt(num.toString()));
}
//如果不是运算符也不是操作数，判断是否为括号
else if (isBracket(ch)){
//如果是括号，判断左括号压入运算符栈
if (ch=='('){
operatorStack.push(ch);
}
//如果是右括号，依次弹出s1的运算符，压入结果栈，直到遇见左括号（丢弃这一对括号）
else if (ch==')'){
while (true){
int top = operatorStack.pop();
if (top=='('){
break;
}
resStack.push(top);
}
}
}
}
//遍历结束后，将运算符栈中剩余的运算符依次弹出压入结果栈
while (!operatorStack.isNull()){
resStack.push(operatorStack.pop());
}
//遍历结果栈返回后缀表达式字符串(这里是反的)
StringBuilder res = new StringBuilder();
while (!resStack.isNull()){
int pop = resStack.pop();
if (isOperator(pop)){
char popChar = (char) pop;
res.append(popChar).append(" ");
}else {
res.append(pop).append(" ");
}
}
//将结果字符串反转返回后缀表达式
String s = res.toString();
String[] s1 = s.split(" ");
StringBuilder builder = new StringBuilder();
for (int i = s1.length-1; i >= 0; i--) {
builder.append(s1[i]).append(" ");
}
return builder.toString();
}
思考：
最后出栈顺序的倒叙才是后缀表达式，那么是否可以用队列来代替s2栈呢？
是完全可以的，s2在整个过程只有入栈操作，更换为队列进行入队，最终栈先进后出是逆序，队列先进先出就是顺序的。
评论(0)