【数据结构C++】表达式求值(多位数)课程设计


📚博客主页:Zhui_Yi_
🔍:上期回顾:图

❤️感谢大家点赞👍🏻收藏⭐评论✍🏻,您的三连就是我持续更新的动力❤️
🎇追当今朝天骄,忆顾往昔豪杰。
在这里插入图片描述

文章目录

  • 前言
    • 问题描述
    • 基 本 要 求
    • 实 现 提 示
  • 一、摘要以及引言
    • 摘要
    • 引言
  • 二、系统设计
  • 三、关键算法与实现
    • 1.运算符处理
    • 2.表达式求值流程
  • 四、程序实现
  • 五、具体代码
    • 1.定义结构以及初始化
    • 2.简单的链栈操作
      • 判空
      • 入栈
      • 出栈
      • 取栈顶元素
      • 判断运算符是否有效
      • 将运算符转换
      • 判断运算符优先级
      • 进行运算
      • 进行运算
      • 完整代码
  • 总结
  • 切记切记,我给出代码缺少对括号匹配的信息,但代码是能直接运行的,需要你们自己写出来。

前言

本期呢,给大家带来的课程设计,简单给大家说一哈要求:

问题描述

任 何 一 个 表 达 式 都 是 由 操 作 数 (operand)、 运 算 符 (operator)和 界 限 符
(delimiter)组 成 的 。 其 中 , 操 作 数 可 以 是 常 量 , 也 可 以 是 变 量 ; 运 算 符 可 以 是 算
术 运 算 符 、关 系 运 算 符 和 逻 位 算 符 ;界 限 符 是 左 、右 括 号 和 标 志 表 达 式 结 束 的 结 束 符。
在 本 课 程 设 计 中 ,仅 讨 论 简 单 算 术 表 达 式 的 求 值 问 题 , 约 定 表 达 式 中 只 包 含 加 、减 、 乘 、 除 4 种运算, 所 有 的 运 算 对 象 均 为 简 单 变 量 , 表 达 式 的 结 束 符 为 “ =”。
要 求以 字 符 序 列 的 形 式 从 终 端 输 入 语 法 正 确 、不 含 变 量 的 整 数 表 达 式 。 利 用 已 知 的 运 算 符 优 先 关 系 , 实 现 对 算 术 表 达 式 的 求 值 。

基 本 要 求

这 是 一 个 利 用 栈 结 构 完 成 的 程 序 。为 了 实 现 运 算 符 优 先 算 法 ,需 使 用 两 个 工 作 栈 ,一 个 称 为 运 算 符 栈 (OPTR), 用 来 寄 存 运 算 符 ; 另 一 个 称 为 操 作 数 栈 (OPND), 用 来
寄 存 操 作 数 或 运 算 结 果 。 基 本 要 求 如 下 : (1) 表 达 式 中 只 包 含 加 、 减 、 乘 、 除 4
种 运 算 , 应 按 优 先 级 进 行 运 算 。
(2) 表 达 式 中 不 包 含 变 量 。
(3) 操 作 数 应 为 整 数
(4) 操 作 数 应 包 含 1 位 数 , 2 位 数 , 3 位 数 等 不 同 数 据 。
(5) 初 始 状态: 操作数栈(OPND)为空栈,表达式结束符“ =” 为 运 算 符 栈 (OPTR)的 栈 底 元 素 。

实 现 提 示

假 设 算 术 表 达 式 Expression 内 可 以 含 有 常 量 (0~9)和 二 元 运 算 符(+, -, *, /)。 实
现 以 下 操 作 : (1) ReadExpre(E): 对 以字符序列的形式输入语法正确的 中 缀表 达 式 并 构 造 表 达 式 E。
(2) EValuation(): 对 算 术 表 达 式 E 求 值 。 (3) Compare(c1,c2): 比 较 运 算 符
优 先 级 。
(4) Operate(a,optr,b):根 据 运 算 符 optr 进 行 操 作 数 a 和 b 的 运算 。
(5) 栈 的 相 关 操 作 ( 必 须 自 己 实 现 , 不 可 使 用 现 成 的 模 板 类 )。

一、摘要以及引言

摘要

本文介绍了一个利用链栈数据结构实现的简单中缀表达式求值程序。该程序能够接收用户输入的数学表达式,支持加减乘除四则运算及括号,以等号“=”作为输入结束标志,计算表达式的值并输出结果。本文详细阐述了程序的设计思路、核心算法及实现细节,旨在为初学者提供一个学习链栈应用和表达式求值原理的实践案例。

引言

在计算机科学领域,表达式求值是一项基本而重要的任务,广泛应用于编译器设计、计算器开发等多个场景。其中,中缀表达式是最自然的数学表达形式,但直接计算中缀表达式较为复杂。本文采用栈这一数据结构,设计并实现了一个程序,能够高效地将中缀表达式转换为后缀表达式(逆波兰表示法),进而计算其值。

二、系统设计

  • 本系统主要由以下几个部分组成:
  • 链栈结构:定义了两个链栈,OPTD用于存储操作数,OPTR用于存储运算符。
    表达式解析与计算:程序首先读取用户输入的中缀表达式,然后根据运算符优先级和括号规则,将表达式转换为便于计算的形式,并最终求得结果。
    用户交互:提供友好界面,用户输入表达式,以等号结束,程序显示计算结果,并询问是否继续进行新的计算。

三、关键算法与实现

1.运算符处理

  • 运算符入栈规则:程序通过Precede函数判断新读入的运算符与栈顶运算符的优先级,优先级较低的运算符先出栈计算。
    括号处理:遇到左括号入栈,遇到右括号则弹出栈顶运算符直到遇到左括号,处理括号内表达式。
    等号处理:等号既是输入结束标志,也作为特殊运算符处理,确保表达式正确结束。

2.表达式求值流程

  1. 初始化:初始化两个链栈。
  2. 读取输入:逐字符读取用户输入的表达式。
  3. 字符处理:对每个字符判断是否为运算符、数字或结束符号,进行相应处理。
  4. 运算符优先级判定与操作数计算:使用栈结构辅助计算,遵循运算符优先级规则。
  5. 输出结果:计算完成后,输出表达式的计算结果。

四、程序实现

本程序使用C++语言实现,主要采用了结构体定义链栈,通过自定义的链栈操作函数实现了数据的入栈、出栈等操作。calculate函数为核心,负责解析和计算表达式。通过一系列条件判断和循环结构,实现了对中缀表达式的有效处理。此外,程序还包含用户交互环节,提高了用户体验。

五、具体代码

1.定义结构以及初始化

// 链栈节点结构
struct Node {double data;Node* next;
};// 链栈结构
struct LinkStack {Node* top;int size;
};// 初始化链栈
LinkStack* InitLinkStack() {LinkStack* stack = new LinkStack;stack->top = nullptr;stack->size = 0;return stack;
}

2.简单的链栈操作

判空

bool IsEmpty(LinkStack* stack) {return stack->top == nullptr;
}

入栈

// 入栈操作
void Push(LinkStack* stack, double value) {Node* node = new Node;node->data = value;node->next = stack->top;stack->top = node;stack->size++;
}

出栈

double Pop(LinkStack* stack) {if (IsEmpty(stack)) {throw runtime_error("栈是空的!");}double value = stack->top->data;Node* temp = stack->top;stack->top = stack->top->next;delete temp;stack->size--;return value;
}

取栈顶元素

// 获取栈顶元素
double GetTop(LinkStack* stack) {if (IsEmpty(stack)) {throw runtime_error("栈是空的!");}return stack->top->data;
}

判断运算符是否有效

运算符分为+、-、*、/、=,即:

bool In(char c) {if (c == '(' || c == ')' || c == '+' || c == '-' || c == '*' || c == '/' || c == '=')return true;return false;
}

将运算符转换

int intdata(char c) {switch (c) {case '+': return 0;case '-': return 1;case '*': return 2;case '/': return 3;case '(': return 4;case ')': return 5;case '=': return 6; default: break;}
}

判断运算符优先级

在这里插入图片描述
根据这张图片进行建立二维数组。

char Precede(char c1, char c2) {int a, b;char table[7][7] = {'>','>','<','<','<','>','>','>','>','<','<','<','>','>','>','>','>','>','<','>','>','>','>','>','>','<','>','>','<','<','<','<','<','=','0','>','>','>','>','0','>','>','<','<','<','<','<','0','=',};a = intdata(c1); b = intdata(c2);return table[a][b];
}

进行运算

double operate(double a, char c, double b) {if (c == '+') return (a + b);else if (c == '-') return (a - b);else if (c == '*') return (a * b);else if (c == '/') {if (b == 0) return (flag = 1);else return (a / b);}
}

进行运算

double calculate() {char ch, tempc;double x, y, temp, count = 0;Push(OPTR, '='); cin >> ch;while (ch != '=' || GetTop(OPTR) != '=') { if (!In(ch)) {if (count != 0) {temp = GetTop(OPTD); Pop(OPTD);temp = (double)(temp * 10 + ch - '0');Push(OPTD, temp);cin >> ch;}else {temp = (double)(ch - '0');Push(OPTD, temp);count++;cin >> ch;}}else {count = 0;switch (Precede(GetTop(OPTR), ch)) {case '<':Push(OPTR, ch);cin >> ch;break;case '>':tempc = GetTop(OPTR); Pop(OPTR);y = GetTop(OPTD); Pop(OPTD);x = GetTop(OPTD); Pop(OPTD);Push(OPTD, operate(x, tempc, y));break;case '=':tempc = GetTop(OPTR); Pop(OPTR);cin >> ch;break;default:break;}}}return GetTop(OPTD);
}

完整代码

#include <iostream>
#include <string>using namespace std;// 链栈节点结构
struct Node {double data;Node* next;
};// 链栈结构
struct LinkStack {Node* top;int size;
};// 初始化链栈
LinkStack* InitLinkStack() {LinkStack* stack = new LinkStack;stack->top = nullptr;stack->size = 0;return stack;
}// 判断栈是否为空
bool IsEmpty(LinkStack* stack) {return stack->top == nullptr;
}// 入栈操作
void Push(LinkStack* stack, double value) {Node* node = new Node;node->data = value;node->next = stack->top;stack->top = node;stack->size++;
}// 出栈操作
double Pop(LinkStack* stack) {if (IsEmpty(stack)) {throw runtime_error("栈是空的!");}double value = stack->top->data;Node* temp = stack->top;stack->top = stack->top->next;delete temp;stack->size--;return value;
}// 获取栈顶元素
double GetTop(LinkStack* stack) {if (IsEmpty(stack)) {throw runtime_error("栈是空的!");}return stack->top->data;
}// 全局链栈
LinkStack* OPTD = InitLinkStack();
LinkStack* OPTR = InitLinkStack();
int flag = 0;// 判断字符是否为运算符
bool In(char c) {if (c == '(' || c == ')' || c == '+' || c == '-' || c == '*' || c == '/' || c == '=')return true;return false;
}// 将运算符转换为序号
int intdata(char c) {switch (c) {case '+': return 0;case '-': return 1;case '*': return 2;case '/': return 3;case '(': return 4;case ')': return 5;case '=': return 6; // 修改这里,添加'='的序号default: break;}
}// 判定运算符优先级
char Precede(char c1, char c2) {int a, b;char table[7][7] = {'>','>','<','<','<','>','>','>','>','<','<','<','>','>','>','>','>','>','<','>','>','>','>','>','>','<','>','>','<','<','<','<','<','=','0','>','>','>','>','0','>','>','<','<','<','<','<','0','=',};a = intdata(c1); b = intdata(c2);return table[a][b];
}// 执行运算
double operate(double a, char c, double b) {if (c == '+') return (a + b);else if (c == '-') return (a - b);else if (c == '*') return (a * b);else if (c == '/') {if (b == 0) return (flag = 1);else return (a / b);}
}// 表达式求值
double calculate() {char ch, tempc;double x, y, temp, count = 0;Push(OPTR, '='); cin >> ch;while (ch != '=' || GetTop(OPTR) != '=') { if (!In(ch)) {if (count != 0) {temp = GetTop(OPTD); Pop(OPTD);temp = (double)(temp * 10 + ch - '0');Push(OPTD, temp);cin >> ch;}else {temp = (double)(ch - '0');Push(OPTD, temp);count++;cin >> ch;}}else {count = 0;switch (Precede(GetTop(OPTR), ch)) {case '<':Push(OPTR, ch);cin >> ch;break;case '>':tempc = GetTop(OPTR); Pop(OPTR);y = GetTop(OPTD); Pop(OPTD);x = GetTop(OPTD); Pop(OPTD);Push(OPTD, operate(x, tempc, y));break;case '=':tempc = GetTop(OPTR); Pop(OPTR);cin >> ch;break;default:break;}}}return GetTop(OPTD);
}// 菜单函数
void menu() {puts("\n=========================\n");puts("       表达式求值");puts("\n=========================\n");
}// 主函数
int main() {menu();double answer, trueValue = 1;while (trueValue) {cout << "\n请输入表达式,以等号(=)结束:"; answer = calculate();if (flag == 1) {cout << "分母不能为0哦!" << endl;flag = 0;}elsecout << "表达式的值为:" << answer << endl;cout << "按0可结束程序,继续请按1:";cin >> trueValue;}return 0;
}

在这里插入图片描述

总结

本文通过设计链栈数据结构和实现相应的算法,成功开发了一个能够处理中缀表达式的程序。该程序不仅能够正确计算表达式的值,还具备良好的用户交互体验,适合教学和初步编程实践。未来的工作可以考虑扩展程序功能,支持更多类型的运算符和更复杂的表达式结构。

切记切记,我给出代码缺少对括号匹配的信息,但代码是能直接运行的,需要你们自己写出来。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/353530.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

房地产房型展示信息小程序的内容是什么

地产业规模之大且品牌众多&#xff0c;还有房屋租赁、中介等&#xff0c;无论开发商公司还是衍生行业商家都需要多渠道宣传品牌和客户触达沟通转化&#xff0c;除了线下各种传单&#xff0c;线上也是主要场景&#xff0c;通过各种连接来达到相应目标。 也因此需符合平台生态开…

人工智能--自然语言处理NLP概述

欢迎来到 Papicatch的博客 目录 &#x1f349;引言 &#x1f348;基本概念 &#x1f348;核心技术 &#x1f348;常用模型和方法 &#x1f348;应用领域 &#x1f348;挑战和未来发展 &#x1f349;案例分析 &#x1f348;机器翻译中的BERT模型 &#x1f348;情感分析在…

iCopy for Mac 剪切板 粘贴工具 历史记录 安装(保姆级教程,新手小白轻松上手)

Mac分享吧 文章目录 效果可留存文本、图片、文件等复制历史记录也可根据关键字进行历史记录检索点击一下&#xff0c;可复制双击两下&#xff0c;复制内容&#xff0c;并将信息粘贴至鼠标指针处 一、准备工作二、开始安装1、双击运行软件&#xff0c;将其从左侧拖入右侧文件夹…

【包管理】Node.JS与Ptyhon安装

文章目录 Node.JSPtyhon Node.JS Node.js的安装通常包括以下几个步骤&#xff1a; 访问Node.js官网&#xff1a; 打开Node.js的官方网站&#xff08;如&#xff1a;https://nodejs.org/zh-cn/download/&#xff09;。 下载安装包&#xff1a; 根据你的操作系统选择对应的Node…

Kotlin编程实践-【Java如何调用Kotlin中带默认值参数的函数】

问题 如果你有一个带有默认参数值的 Kotlin 函数&#xff0c;如何从 Java 调用它而无须为每个参数显式指定值&#xff1f; 方案 为函数添加注解JvmOverloads。 也就是为Java添加重载方法&#xff0c;这样Java调用Kotlin的方法时就不用传递全部的参数了。 示例 在 Kotlin …

python中scrapy

安装环境 pip install scrapy 发现Twisted版本不匹配 卸载pip uninstall Twisted 安装 pip install Twisted22.10.0 新建scrapy项目 scrapy startproject 项目名 注意&#xff1a;项目名称不允许使用数字开头&#xff0c;也不能包含中文 eg: scrapy startproject scrapy_baidu_…

【vue baidu-map】解决更新数据,bm-marker显示不完全问题

实现效果&#xff1a; 问题&#xff1a;切换上面基地tab键&#xff0c;导致地图图标展示不完全&#xff1b;刷新页面就可以正常展示。判断是<bm-marker>标记元素没有动态刷新dom元素引起的问题。 方案&#xff1a;this.$nextTick({}) this.$nextTick(()>{this.equipm…

Python复数的加、减、乘、除运算

一、复数 复数由实部和虚部组成&#xff0c;形如(a,b均为实数)的数为复数&#xff0c;其中&#xff0c;a被称为实部&#xff0c;b被称为虚部&#xff0c;i为虚数单位&#xff0c;。复数通常用z表示&#xff0c;即zabi&#xff0c;当z的虚部b&#xff1d;0时&#xff0c;则z为实…

云电脑有多好用?适合哪些人使用?

云电脑作为一种新型的计算模式&#xff0c;其应用场景广泛且多样&#xff0c;适合各类人群使用。云电脑适合什么人群使用&#xff1f;云电脑有哪些应用场景&#xff1f;有什么好的云电脑推荐&#xff1f;以下本文将详细探讨云电脑的主要应用场景及其适用人群的相关内容&#xf…

怎样搭建serveru ftp个人服务器

首先说说什么是ftp&#xff1f; FTP协议是专门针对在两个系统之间传输大的文件这种应用开发出来的&#xff0c;它是TCP/IP协议的一部分。FTP的意思就是文件传输协议&#xff0c;用来管理TCP/IP网络上大型文件的快速传输。FTP早也是在Unix上开发出来的&#xff0c;并且很长一段…

【Android】基于webView打造富文本编辑器(H5)

目录 前言一、实现效果二、具体实现1. 导入网页资源2. 页面设计3. 功能调用4. 完整代码 总结 前言 HTML5是构建Web内容的一种语言描述方式。HTML5是Web中核心语言HTML的规范&#xff0c;用户使用任何手段进行网页浏览时看到的内容原本都是HTML格式的&#xff0c;在浏览器中通过…

Boosting原理代码实现

1&#xff0e;提升方法是将弱学习算法提升为强学习算法的统计学习方法。在分类学习中&#xff0c;提升方法通过反复修改训练数据的权值分布&#xff0c;构建一系列基本分类器&#xff08;弱分类器&#xff09;&#xff0c;并将这些基本分类器线性组合&#xff0c;构成一个强分类…

什么是拷贝?我:Ctrl + C ...

前言 当谈及拷贝&#xff0c;你的第一印象会不会和我一样&#xff0c;ctrl c ctrl v ... &#xff1b;虽然效果和拷贝是一样的&#xff0c;但是你知道拷贝的原理以及它的实现方法吗&#xff1f;今天就让我们一起探究一下拷贝中深藏的知识点吧。 拷贝 首先来看下面一段代码…

Vue10-实战快速上手

实战快速上手 我们采用实战教学模式并结合ElementUI组件库&#xff0c;将所需知识点应用到实际中&#xff0c;以最快速度带领大家掌握Vue的使用&#xff1b; 1、创建工程 注意&#xff1a;命令行都要使用管理员模式运行 1、创建一个名为hello-vue的工程vue init webpack hel…

iview 组件里面的(任何一个月)整月日期全部选中_iview时间轴选中有历史记录日期

iview 组件里面的整月日期全部选中&#xff1a; ①&#xff1a;第一种是当前月的日期全部选中&#xff1a; 先上效果图&#xff1a;当前月分 获取到的值&#xff1a; 当前月的方法&#xff1a; // getDateStr() {// var curDate new Date();// var curMonth curDate.ge…

【HTML01】HTML基础-基本元素-附带案例-作业

文章目录 HTML 概述学HTML到底学什么HTML的基本结构HTML的注释的作用html的语法HTML的常用标签&#xff1a;相关单词参考资料 HTML 概述 英文全称&#xff1a;Hyper Text Markup Language 中文&#xff1a;超文本标记语言&#xff0c;就将常用的50多个标记嵌入在纯文本中&…

python pytest 参数化的几种方式

一、使用pytest.mark.parametrize装饰器&#xff1a; 可以使用pytest提供的pytest.mark.parametrize装饰器来指定参数化测试的参数。下面是一个示例&#xff1a; import pytest# pytest.mark.parametrize装饰器 # 其中num expected&#xff0c;分别对应(1, 1),(2, 4),(3, 9)&…

c语言中的字符函数

1.字符分类函数 c语言中有一系列函数是专门做字符分类的&#xff0c;也就是一个字符属于什么类型的字符。这些函数的使用需要包含一个头文件是ctype.h 可能你看这些感觉很懵&#xff0c;我以islower举例 #include<ctype.h> int main() {int retislower(A);printf("…

Git记录 上传至Gitee

1.GitHub拉去的代码需要上传至自己的Gitee需要清除原有remote服务器信息 查看原始远程服务器信息&#xff0c;后删除远程服务器信息 git remote -v git remote rm origin 2.Gitee新建软件仓库 法1&#xff09;不用初始化仓库&#xff0c;初始化会自动生成.git。如果本地.git…

Qt项目天气预报(3) - qt的http编程获取天气数据

概念 Qt中的HTTP编程主要涉及使用Qt的网络模块来进行HTTP请求和处理HTTP响应。Qt提供了一系列类来处理网络通信&#xff0c;其中最常用的类是 QNetworkAccessManager 、 QNetworkRequest 、 QNetworkReply 以及相关的支持类。 编程实例 以下是一个基本的HTTP编程示例&#xff0…