栈的应用-综合计数器的实现
目录
前言
在实现综合计数器之前,大家应该先了解一下什么是前中后缀表达式
前缀、中缀和后缀表达式是表示数学表达式的三种不同方式。
-
前缀表达式（也称为波兰式或前缀记法）：操作符位于操作数之前。例如，"+ 2 3"表示加法操作，其中2和3是操作数。
-
中缀表达式：操作符位于操作数之间。这是我们通常使用的数学表达式表示方式。例如，"2 + 3"表示加法操作，其中2和3是操作数。
-
后缀表达式（也称为逆波兰式或后缀记法）：操作符位于操作数之后。例如，"2 3 +"表示加法操作，其中2和3是操作数。
这三种表达式都可以表示相同的数学运算，只是操作符和操作数的排列顺序不同。在计算机中，后缀表达式常用于数学表达式的求值，因为它可以通过使用栈来进行简单而高效的计算。
本次实现综合计算器就是借助后缀表达式来实现,为了简单起见,我们并不加入()等的符号
一、思路分析
定义两个栈,一个栈为数栈(NumStack)用来存放数字,另一个栈为符号栈,用来存放符号
1. 通过一个 index 值（索引），来遍历我们的表达式
2. 如果我们发现是一个数字, 就直接入数栈
3. 如果发现扫描到是一个符号, 就分如下情况
3.1 如果发现当前的符号栈为 空，就直接入栈
3.2 如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符， 就需要从数栈中pop出两个数,在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈， 如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈.
4. 当表达式扫描完毕，就顺序的从 数栈和符号栈中pop出相应的数和符号，并运行.
5. 最后在数栈只有一个数字，就是表达式的结果
我们来举个例子 图解 计算 7*2*2-5+1 = 24
二、代码实现
代码量太大,不可能一步一步解析了,上面的过程如果能看懂,并且编程有一定基础,下面代码应该不成问题,代码出处033_尚硅谷_栈实现综合计算器-思路分析(1)_哔哩哔哩_bilibili
大家可以去看看
package 逆波兰计数器;import StackDemo.StackEmptyException;import java.util.Arrays;import java.util.Scanner;class Test{ public static void main(String[] args) { String str = "7*2*2-5+1"; ArrayStack numStack = new ArrayStack(10); ArrayStack operaStack = new ArrayStack(10); String s = ""; int nums1 = 0; int nums2 = 0; int index = 0; int opera = 0; char ch = ' '; while (true) { ch = str.charAt(index); // 判断该字符是否是符号 if(operaStack.isOpera(ch)){ // 判断符号栈是否为空 if(!operaStack.isEmpty()){ // 判断优先级 if(operaStack.priority(ch) <= operaStack.priority(operaStack.peek())){ nums1 = numStack.pop(); nums2 = numStack.pop(); opera = operaStack.pop(); int cal = numStack.cal(nums1, nums2, opera); numStack.push(cal); operaStack.push(ch); }else{ operaStack.push(ch); } }else{ // 符号栈为空,直接入栈 operaStack.push(ch); } }else{ boolean flag = true;// 定义标志位 检查字符串是否达到末尾 // 处理非个位数的情况 如 88 66 这样的数 while (!operaStack.isOpera(ch)) { s+=ch; if(index == str.length() -1 ){ numStack.push(Integer.parseInt(s)); flag = false; break; }else { index++; ch = str.charAt(index); } } if(!flag){ break; } numStack.push(Integer.parseInt(s)); s = ""; index--; } index++; if(index>=str.length()){ break; } } while (true) { if(operaStack.isEmpty()){ System.out.println(str+"="+numStack.pop()); break; } nums1 = numStack.pop(); nums2 = numStack.pop(); opera = operaStack.pop(); int cal = numStack.cal(nums1, nums2, opera); numStack.push(cal); } }}public class ArrayStack { private final int capacity; private int top = -1; private int[] stack ; public ArrayStack(int capacity){ this.capacity = capacity; stack = new int[capacity]; } // 入栈 public void push(int data){ if(isFull()){ stack = Arrays.copyOf(stack,capacity*2); } top++; stack[top] = data; } // 出栈 public int pop(){ if(isEmpty()){ throw new StackEmptyException("队列为空,无法删除元素"); } int value = stack[top]; top--; return value; } // 查看栈顶的值 public int peek(){ return stack[top]; } // 制定优先级规则 public int priority(int opera){ if(opera == '*' || opera == '/'){ return 1; }else if(opera == '+' || opera == '-'){ return 0; }else{ return -1; } } // 判断是否为运算符 public boolean isOpera(int val){ return val == '+' || val == '-' || val == '*' || val == '/'; } // 运算方法 public int cal(int num1,int num2,int opera){ return switch (opera) { case '+' -> num1 + num2; case '-' -> num2 - num1; case '*' -> num1 * num2; case '/' -> num2 / num1; default -> -1; }; } public boolean isFull(){ return top == capacity - 1; } public boolean isEmpty(){ return top == - 1; }}总结
关于栈的应用远不止于此,大家也不必全部了解,只要能运用到这种程度,在刷点面试题,应付面试足矣!
来源地址：https://blog.csdn.net/weixin_73869209/article/details/132791952
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
