当前位置: 首页 > web >正文

数据结构与算法之中缀表达式的求值

栈的一个实际需求
  • 请输入一个表达式
  • 计算式:[7*22-5+1-53-3]点击计算【如下图】
    栈的应用
栈的介绍
  • 栈的英文为stack(stack)。
  • 栈是一个先入后出(FILO-First In Last Out)的有序列表。
  • 栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除一端,为变化的一端,称为栈顶(Top),另一端为固定的一端,称为栈底(Bottom)
  • 根据栈的定义可知,最先放入栈中元素在栈底,最后放入的元素在栈顶。而删除元素刚好相反,最后放入的元素最先删除,最先放入的元素最后删除。
  • 图解说明出栈(pop)和入栈(push)的概念
    栈
  • 栈的应用场景
    • 子程序的调用:在跳往子程序前,会先将下个指令的地址存到堆栈中,直到子程序执行完后将地址取出,以回到原来的程序中。
    • 处理递归调用:和子程序的调用类似,只是除了存储下一个指令的地址外,也将参数、区域变量等数据存入堆栈中。
    • 表示的转换[中缀表达式转后缀表达式]与求值(实际解决)
    • 二叉树的遍历。
    • 图形的深度优先(dept-first)搜索法。
栈的快速入门
  • 用数组模拟栈的使用,由于栈是一种有序列表,当然可以使用数组的结构来存储栈的数据内容。
  • 栈
    实现思路分析,并画出示意图
import java.util.Scanner;/*** 数组模拟栈*/
public class ArrayStackDemo {public static void main(String[] args) {// 创建一个栈ArrayStack arrayStack = new ArrayStack(3);Scanner scanner = new Scanner(System.in);String key;mywhile:while(true) {System.out.println("push:将一个元素压入栈中");System.out.println("pop:从栈中弹出一个元素");System.out.println("show:显示栈中所有元素");System.out.println("peek:查看栈顶元素");System.out.println("exit:退出系统");System.out.print("请选择你要执行的惭怍:");key = scanner.next();switch(key) {case "push":System.out.println("请选择你要压入栈中的元素");int value = scanner.nextInt();arrayStack.push(value);break;case "pop":try{System.out.println("弹出的元素是:" + arrayStack.pop());}catch(Exception e) {System.out.println(e.getMessage());}break;case "peek":try{System.out.println("栈顶的元素是:" + arrayStack.peek());}catch(Exception e) {System.out.println(e.getMessage());}break;case "show":arrayStack.display();break;case "exit":scanner.close();break mywhile;default:break;}}System.out.println("已退出系统,欢迎下次使用");}
}
class ArrayStack {int top;int[] arrStack;int maxSize;public ArrayStack(int maxSize) {this.maxSize = maxSize;arrStack = new int[maxSize];top = -1;}// 将元素压入栈中public void push(int value) {if(isFull()) {System.out.println("栈已满,不能压入");return;}arrStack[++top] = value;}// 从栈中弹出元素public int pop() {if(isEmpty()) {throw new RuntimeException("栈为空");}return arrStack[top--];}// 查看栈顶元素public int peek() {if(isEmpty()) {throw new RuntimeException("栈为空");}return arrStack[top];}// 遍历栈中所有信息public void display() {if(isEmpty()) {System.out.println("栈空,没有数据");return;}for(int i = top;i >= 0;i--) {System.out.printf("stack[%d]=%d\n",i,arrStack[i]);}}/*** 判断栈是否满* @return*/public boolean isFull() {return top == maxSize - 1;}// 判断栈是否为空public boolean isEmpty() {return top == -1;}
}
  • 练习:使用链表来模拟栈
栈实现综合计算器(中缀表达式)
  • 使用栈来实现综合计算器
    栈
  • 思路分析
    中缀表达式
  • 代码实现
public class InffixExpressionValue {public static void main(String[] args) {// 要求值的表达式String expression = "100-2*3*7-5";// 定义两个栈,一个用来存放操作数,一个用来存放操作符ArrayStack2 numStack = new ArrayStack2(10);ArrayStack2 operStack = new ArrayStack2(10);String keepNum = ""; // 用来拼接多位数int num1 = 0;int num2 = 0;int oper = 0;int res = 0;for(int i = 0; i < expression.length(); i++){char ch = expression.substring(i, i + 1).charAt(0);// 如果是运算符if(operStack.isOper((ch))) {// 判断操作符栈中有没有运算符,没有,直接压入栈中if(operStack.isEmpty()) {operStack.push(ch);continue;}// 有的话比较优先级,依次弹出栈中优先级大于等于ch的,并进行计算while(!operStack.isEmpty() && operStack.priority(ch) <= operStack.priority(operStack.peek())) {num1 = numStack.pop();num2 = numStack.pop();oper = operStack.pop();res = numStack.calculate(num1,num2,oper);numStack.push(res);}// 将该运算符入栈operStack.push(ch);}else {// 如果是数字直接入数栈
//                numStack.push(ch - 48);// 分析思路:// 1.当处理多位数时,不能发现是一个数就立即入栈,因为它可能时多位数// 2.在处理数时,需要向expression的表达式的i后再看一位,如果时数进行扫描。如果是符号才入栈keepNum = keepNum +  ch;while((i + 1 < expression.length())) {char ch1 = expression.substring(i + 1, i + 2).charAt(0);if(operStack.isOper(ch1)) {break;}keepNum = keepNum + ch1;i++;}numStack.push(Integer.parseInt(keepNum));keepNum = "";}}// 依次弹出操作符栈和操作数栈中的数字进行运算while(!operStack.isEmpty()) {num1 = numStack.pop();num2 = numStack.pop();oper = operStack.pop();res = operStack.calculate(num1,num2,oper);numStack.push(res);}// 直到操作数栈为空,弹出操作数栈的元素就是最终结果System.out.printf("表达式%s的值是%d",expression,numStack.pop());}}class ArrayStack2 {int top;int[] arrStack;int maxSize;public ArrayStack2(int maxSize) {this.maxSize = maxSize;arrStack = new int[maxSize];top = -1;}// 将元素压入栈中public void push(int value) {if(isFull()) {System.out.println("栈已满,不能压入");return;}arrStack[++top] = value;}// 从栈中弹出元素public int pop() {if(isEmpty()) {throw new RuntimeException("栈为空");}return arrStack[top--];}// 查看栈顶元素public int peek() {if(isEmpty()) {throw new RuntimeException("栈为空");}return arrStack[top];}// 遍历栈中所有信息public void display() {if(isEmpty()) {System.out.println("栈空,没有数据");return;}for(int i = top;i >= 0;i--) {System.out.printf("stack[%d]=%d\n",i,arrStack[i]);}}/*** 判断栈是否满* @return*/public boolean isFull() {return top == maxSize - 1;}// 判断栈是否为空public boolean isEmpty() {return top == -1;}// 计算,注意num2是左边的操作数,num1是右边的操作数public static int calculate(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;}return result;}/*** 判断是传入的是不是操作符* @param ch* @return*/public static boolean isOper(int ch) {return ch == '+' || ch == '-' || ch == '*' || ch == '/';}public static int priority(int ch) {int priority = -1;switch(ch) {case '*': case '/':priority = 2;break;case '+': case '-':priority = 1;break;}return priority;}
}
  • 练习:给表达式加入小括号
http://www.xdnf.cn/news/10137.html

相关文章:

  • mapbox高阶,PMTiles介绍,MBTiles、PMTiles对比,加载PMTiles文件
  • SSE流式输出使用POST 请求
  • WSP 对CSV文件中E+如何恢复可用方案
  • Hash 的工程优势: port range 匹配
  • 可视化与动画:构建沉浸式Vue应用的进阶实践
  • 机器学习模型:逻辑回归、决策树、随机森林和 XGBoost
  • 龙虎榜——20250530
  • 主流 AI IDE 之一的 Windsurf 使用入门
  • 新中地三维GIS开发智慧城市效果和应用场景
  • Unity3D ET框架游戏脚本系统解析
  • Linux top命令各指标参数详解(AI)
  • 【大模型】Bert应对超长文本
  • 比较二维结构的尺寸分布
  • 基于 HT for Web 的轻量化 3D 数字孪生数据中心解决方案
  • SPL 轻量级多源混算实践 4 - 查询 MongoDB
  • python官网的lambda知识点总结
  • Linux分区与文件系统选择:EXT4与XFS深度解析
  • 老旧设备数据采集破局 AI图像解析如何让质检LIMS系统焕发新生
  • c++数据结构10——map结构详解
  • 日语学习-日语知识点小记-构建基础-JLPT-N4阶段(30):みます
  • 边缘计算网关在管网压力远程调控中的通信协议配置
  • Spine工具入门教程2之导入
  • 第十九章 正则表达式
  • Predixy的docker化
  • Python训练营打卡Day40
  • Golang——2、基本数据类型和运算符
  • MySQL-8.0.42 主从延迟常见原因及解决方法
  • PDF文件转换之输出指定页到新的 PDF 文件
  • java类与类之间的关系
  • 黑马k8s(十七)