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

【Java】构建表达式二叉树和表达式二叉树求值

问题背景

1. 实现一个简单的计算器。通过键盘输入一个包含圆括号、加减乘除等符号组成的算术表达式字符串,输出该算术表达式的值。要求:

(1)系统至少能实现加、减、乘、除等运算;

(2)利用二叉树算法思想求解表达式的值,先构造由表达式构成的二叉树,按中序、后序遍历的方式输出二叉树中的结点,然后再利用通过对二叉树进行后序遍历求解算术表达式的值。

思路描述

  • 构建表达式二叉树:先用栈将算术表达式转成后缀表达式(具体思路参考),再根据后缀表达式构建表达式二叉树,构建过程:从左到右扫描后缀表达式的每个元素:如果当前元素是操作数,则创建一个只包含该操作数的节点,并将该节点压入栈中;如果当前元素是操作符,则创建一个只包含该操作符的节点,并从栈中弹出两个节点作为其左右子节点,再将该节点压入栈中。最后栈中唯一的节点即为根节点。
  • 表达式二叉树求值:后序遍历二叉树,递归计算左右子树的值,代入运算符计算

 代码实现

//二叉链表存储二叉树
public class TreeNode {String value;TreeNode left;TreeNode right;public TreeNode(String value){this.value=value;}public TreeNode(String value, TreeNode left, TreeNode right) {this.value = value;this.left = left;this.right = right;}
}
public class Calculator {private TreeNode root;public Calculator() {root = null;}public Calculator(TreeNode root) {this.root = root;}//中缀转后缀,List中每个元素就是后缀表达式中每个操作数或运算符public static List<String> infixToPostfix(String infixExpression){Stack<Character> operatorStack=new Stack<>();List<String> postfixExpression=new ArrayList<>();for(int i=0;i<infixExpression.length();i++){//如果是数字if(Character.isDigit(infixExpression.charAt(i))){//可能是多位的数StringBuilder temp=new StringBuilder();temp.append(infixExpression.charAt(i));while (++i<infixExpression.length()&&Character.isDigit(infixExpression.charAt(i))){temp.append(infixExpression.charAt(i));}postfixExpression.add(temp.toString());i--;//while判断完后,i多往后挪了一位,所以要-1}//如果是左括号else if(infixExpression.charAt(i)=='('){operatorStack.push(infixExpression.charAt(i));}//如果是右括号,去匹配左括号else if(infixExpression.charAt(i)==')'){while (!operatorStack.empty()&&operatorStack.peek()!='('){postfixExpression.add(operatorStack.pop()+"");}operatorStack.pop();}//如果是+-*/else {//将优先级<=当前运算符优先级的运算符pop出来,追加到后缀表达式中while (!operatorStack.empty()&&getPrecedence(infixExpression.charAt(i))<=getPrecedence(operatorStack.peek())){postfixExpression.add(operatorStack.pop()+"");}operatorStack.push(infixExpression.charAt(i));}}//将栈中剩余的运算符依次pop出来追加到结果中while (!operatorStack.empty()){postfixExpression.add(operatorStack.pop()+"");}return postfixExpression;}//在中缀转后缀时要判断符号优先级private static int getPrecedence(char operator) {switch (operator) {case '+':case '-':return 1;case '*':case '/':case '%':return 2;default:return 0;}}//利用后缀表达式构建表达式二叉树public static TreeNode buildExpressionTree(List<String> postfixExpression){Stack<TreeNode> stack=new Stack<>();//从左至右遍历后缀表达式for(String str:postfixExpression){//如果是运算数if(str.charAt(0)>=48&&str.charAt(0)<=57){TreeNode treeNode = new TreeNode(str, null, null);stack.push(treeNode);} else {//如果是运算符//从栈中弹出两个节点TreeNode pop1 = stack.pop();TreeNode pop2 = stack.pop();TreeNode treeNode = new TreeNode(str, pop1, pop2);stack.push(treeNode);}}//最后栈中剩余的节点就是二叉树根节点return stack.peek();}//中序遍历表达式二叉树(左根右)public static void inorderTraversal(TreeNode treeNode){if(treeNode==null)return;inorderTraversal(treeNode.left);System.out.print(treeNode.value+" ");inorderTraversal(treeNode.right);}//后序遍历表达式二叉树(左右根)public static void postorderTraversal(TreeNode treeNode){if(treeNode==null)return;postorderTraversal(treeNode.left);postorderTraversal(treeNode.right);System.out.print(treeNode.value+" ");}//后序遍历表达式二叉树求值public int evaluateExpression(){return evaluateExpression(root);}public int evaluateExpression(TreeNode root){if(root==null){return 0;}// 递归计算左右子树的值int leftValue = evaluateExpression(root.left);int rightValue = evaluateExpression(root.right);switch (root.value){case "+":return leftValue+rightValue;case "-":return leftValue-rightValue;case "*":return leftValue*rightValue;case "/":return leftValue/rightValue;default:// 如果是操作数,则返回对应的整数值return Integer.valueOf(root.value);}}
}

 运行效果

public class Main {public static void main(String[] args) {System.out.println("请输入你要计算的表达式:");Scanner sc = new Scanner(System.in);String infixExpression = sc.next();List<String> postfixExpression = Calculator.infixToPostfix(infixExpression);//中缀转后缀TreeNode binaryTree = Calculator.buildExpressionTree(postfixExpression);//利用后缀表达式构建表达式二叉树System.out.print("中序遍历:");Calculator.inorderTraversal(binaryTree);//中序遍历System.out.println();System.out.print("后序遍历:");Calculator.postorderTraversal(binaryTree);//后序遍历System.out.println();Calculator calculator = new Calculator(binaryTree);int i = calculator.evaluateExpression();System.out.println("值为:"+i);}
}

 

相关文章:

【Java】构建表达式二叉树和表达式二叉树求值

问题背景 1. 实现一个简单的计算器。通过键盘输入一个包含圆括号、加减乘除等符号组成的算术表达式字符串&#xff0c;输出该算术表达式的值。要求&#xff1a; &#xff08;1&#xff09;系统至少能实现加、减、乘、除等运算&#xff1b; &#xff08;2&#xff09;利用二叉…...

采用Python 将PDF文件按照页码进行切分并保存

工作中经常会遇到 需要将一个大的PDF文件 进行切分&#xff0c;比如仅需要大PDF文件的某几页 或者连续几页&#xff0c;一开始都是用会员版本的WPS&#xff0c;但是对于程序员&#xff0c;就是要采用技术白嫖 这里就介绍一个 python的PDF 包 PyPDF2 其安装方式也很简单 p…...

H264视频编码原理

说到视频&#xff0c;我们首先想到的可能就是占内存。我们知道一个视频是由一连串图像序列组成的&#xff0c;视频中图像一般是 YUV 格式。假设有一个电影视频&#xff0c;分辨率是 1080P&#xff0c;帧率是 25fps&#xff0c;并且时长是 2 小时&#xff0c;如果不做视频压缩的…...

UDP实现群聊

代码&#xff1a; import java.awt.*; import java.awt.event.*; import javax.swing.*; import java.net.*; import java.io.IOException; import java.lang.String;public class liaotian extends JFrame{private static final int DEFAULT_PORT8899;private JLabel stateLB…...

服务器部署网易开源TTS | EmotiVoice部署教程

一、环境 ubuntu 20.04 python 3.8 cuda 11.8二、部署 1、docker方式部署 1.1、安装docker 如何安装docker&#xff0c;可以参考这篇文章 1.2、拉取镜像 docker run -dp 127.0.0.1:8501:8501 syq163/emoti-voice:latest2、完整安装 安装python依赖 conda create -n Emo…...

贪心算法和动态规划

目录 一、简介 二、贪心算法案例&#xff1a;活动选择问题 1.原理介绍 三、动态规划案例&#xff1a;背包问题 1.原理介绍 四、贪心算法与动态规划的区别 五、总结 作者其他文章链接 正则表达式-CSDN博客 深入理解HashMap&#xff1a;Java中的键值对存储利器-CSDN博客…...

jsp 设备预约管理系统Myeclipse开发mysql数据库web结构java编程计算机网页项目

一、源码特点 JSP 设备预约管理系统是一套完善的java web信息管理系统&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为 TOMCAT7.0,Myeclipse8.5开发&#xff0c;数据库为Mysql5.0…...

Python:核心知识点整理大全10-笔记

目录 5.4 使用 if 语句处理列表 5.4.1 检查特殊元素 toppings.py 5.4.2 确定列表不是空的 5.4.3 使用多个列表 5.5 设置 if 语句的格式 5.6 小结 第6章 字 典 6.1 一个简单的字典 alien.py 6.2 使用字典 6.2.1 访问字典中的值 6.2.2 添加键—值对 6.2.3 先创建一…...

Hive数据库系列--Hive数据类型/Hive字段类型/Hive类型转换

文章目录 一、Hive数据类型1.1、数值类型1.2、字符类型1.3、日期时间类型1.4、其他类型1.5、集合数据类型1.5.1、Struct举例1.5.2、Array举例1.5.3、Map举例 二、数据类型转换2.1、隐式转换2.2、显示转换 三、字段类型的使用3.1、DECIMAL(precision&#xff0c;scale) 本章主要…...

在Spring Cloud中使用组件Ribbon和Feign,并分别创建子模块注册到Eureka中去

ok&#xff0c;在上篇文章中我们讲了在Spring cloud中使用Zuul网关&#xff0c;这篇文章我们将Spring Cloud的五大核心组件的Ribbon和Feign分别创建一个微服务模块。 题外话&#xff0c;本篇博客就是配置子模块&#xff0c;或者说是微服务&#xff0c;然后将微服务正式启动之前…...

(JAVA)-缓冲流

缓冲流能高效的读取数据 缓冲流底层自带了8192的缓冲区提高性能&#xff0c;他在原有的流上进行了包装&#xff0c;加上了缓冲效果 原理&#xff1a; 读入时首先会将内存中缓冲区大小的数据读入缓冲区中&#xff0c;接着下次读取直接从缓冲区中读取数据&#xff0c;当缓冲区…...

Autosar UDS-CAN诊断开发02-1(CAN诊断帧格式类型详解、CANFD诊断帧格式类型详解、15765-2(CANTP层)的意义)

目录 前言 CANTP层&#xff08;15765-2协议&#xff09;存在的意义 CANTP层&#xff08;15765-2协议&#xff09;帧类型详细解读&#xff08;普通CAN格式&#xff09; 四种诊断报文类型 单帧SingleFrame(SF) 首帧&#xff1a;FirstFrame(FF) 流控帧&#xff1a;FlowCont…...

swing快速入门(三)

解答一下上一篇关于留下的关于布局管理器的疑问 上一篇 几种常见的布局管理器 看不懂&#xff1f;看不懂没关系&#xff0c;这篇是概念篇&#xff0c;大概了解一下就行~ 1.FlowLayout&#xff08;流式布局&#xff09;&#xff1a;按照从左到右、从上到下的顺序依次排列组件。…...

Swagger PHP Thinkphp 接口文档

安装 1. 安装依赖 composer require zircote/swagger-php 2. 下载Swagger UI git clone https://github.com/swagger-api/swagger-ui.git 3. 复制下载好的Swagger UI 中的dist目录到public目录中&#xff0c;修改目录名称 cp -rf swagger-ui/dist /home/htdocs/public/ m…...

12.9每日一题(备战蓝桥杯循环结构)

12.9每日一题&#xff08;备战蓝桥杯循环结构&#xff09; 题目 2165: 求平均年龄题目描述输入输出样例输入样例输出来源/分类 题解 2165: 求平均年龄题目 2166: 均值题目描述输入输出样例输入样例输出来源/分类 题解 2166: 均值题目 2167: 求整数的和与均值题目描述输入输出样…...

与时代共进退

还记得当初自己为什么选择计算机&#xff1f; 当初你问我为什么选择计算机&#xff0c;我笑着回答&#xff1a;“因为我梦想成为神奇的码农&#xff01;我想像编织魔法一样编写程序&#xff0c;创造出炫酷的虚拟世界&#xff01;”谁知道&#xff0c;我刚入门的那天&#xff0…...

Python 云服务器应用,Https,定时重启

Python 云服务器应用,Https,定时重启 环境搭建Python模块模块导入生成Flask实例GET处理启动服务器打开网页验证 GET接入证书 支持https申请证书下载证书保留 xxx.crt 和 xxx.key文件就可以了 copy到python项目目录ssl_context 配置 宝塔面板操作在www目录下新建python工作目录在…...

pytorch 笔记:dist 和 cdist

1 dist 1.1 基本使用方法 torch.dist(input, other, p2) 计算两个Tensor之间的p-范数 1.2 主要参数 input输入张量other另一个输入张量p范数 input 和 other的形状需要是可广播的 1.3 举例 import torchxtorch.randn(4) x #tensor([ 1.2698, -0.1209, 0.0462, -1.3271…...

Java的List中的各种浅拷贝和深拷贝问题

先来看一组代码 public class Temp{public static void main(String[] args) {List<Integer> list new ArrayList<>();list.add(1);list.add(2);list.add(3);List<Integer> temp list;list.add(4);System.out.println(list.toString());System.out.print…...

20231207_最新已测_Centos7.4安装nginx1.24.0_安装详细步骤---Linux工作笔记066

以前安装的太模糊了,干脆重新写一个: 1.首先下载对应的nginx-1.24.0.tar.gz安装文件 2.然后: 去执行命令 安装依赖 yum install -y gcc yum install -y pcre pcre-devel yum install -y zlib zlib-devel yum install -y openssl openssl-devel 3.然后:去解压 tar -zxvf ngi…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...