用栈实现表达式计算

一、设计思想

算法一：

利用栈将中缀表达式转化成后缀表达式再进行计算。

（1）构造char类型的栈函数以及栈的相关函数（出栈函数、进栈函数、创建栈函数、销毁栈函数、判断栈是否为空函数、看栈顶函数等）。

（2）在main函数中让用户进行输入，将用户输入的字符串进行循环、判断（如果数字字符后面的是运算符，则在数字字符后加“#”以便进行区分；否则，

继续循环。）并将判断后的字符串传递到新的数组中，循环结束后，再将数组

传递给中缀表达式转后缀表达式函数（Min_Back()）。

（3）中缀表达式转后缀表达式函数是利用运算符的优先级进行判断来将中缀表达式转换成后缀表达式的函数。函数中利用构建的栈以及栈的相关函数对运

算符进行操作：先看栈顶，如果栈为空或栈顶元素为‘（’或者栈顶元素为‘+’

或‘—’并且现有运算符为‘*’、‘/’或‘%’又或是现有运算符为‘（’，

则现有元素进栈；否则，再对现有元素进行判断：如果现有元素为‘）’，运

算符出栈直到‘（’出栈；否则，运算符出栈直到栈空或者栈顶元素的优先级

低于现有运算符，现有运算符才进栈。循环结束后，将栈中的运算符全部依

次输出，最后将后缀表达式传递给求值函数（countfor()），再销毁栈。

（4）求值函数中首先是利用strtod()函数将数字字符串转换成double类型的数字，然后构建一个数字栈，将转换后的数字传递到栈中，每当遇到运算符时，就

从数字栈中“扔出”两个数字进行相应的运算，循环结束后，将数字栈中的

数字“扔出”，并输出成为表达式最终的结果。

算法二：

利用创建的两个栈直接对表达式进行计算。

（1）分别构建一个char类型和一个double类型的栈函数以及栈的相关函数（出栈函数、进栈函数、创建栈函数、销毁栈函数、判断栈是否为空函数、看栈

顶函数等）。

（2）在main函数中让用户进行输入，将用户输入的字符串进行循环、判断（如果数字字符后面的是运算符，则在数字字符后加“#”以便进行区分；否则，

继续循环。）并将判断后的字符串传递到新的数组中，循环结束后，再将数组

传递给中缀表达式转后缀表达式函数（Countfor ()）。

（3）在Countfor()函数中先创建一个数字栈和一个符号栈，对表达式进行循环，直到元素为’\0’。在循环中如果元素为数字、点或者#，将元素赋给新的数组

Consist[]，再判断下一个元素是否为#，若是则利用strtod()函数将数组中的字

符串转换成double类型的数字，然后数字进栈，清空数组Consist[]；否则，

继续判断。若元素不为数字、点或者#，则先看栈顶，如果栈为空或栈顶元素

为‘（’或者栈顶元素为‘+’或‘—’并且现有元素为‘*’、‘/’或‘%’

又或是现有元素为‘（’，则现有元素进栈；否则，再对现有元素进行判断：

如果现有元素为‘）’，运算符出栈直到‘（’出栈；否则，运算符出栈直到栈

空或者栈顶元素的优先级低于现有运算符，现有运算符才进栈。每当有一个

运算符出栈，就从数栈中取两个数与运算符一起传递给Judge()函数,并将函数

的返回值压入栈中。循环结束后，将栈中的运算符全部依次输出，每当有一

个运算符出栈，就从数栈中取两个数与运算符一起传递给Judge()函数,并将函

数的返回值压入栈中，最后输出数字栈中的数字成为表达式的最终结果，再

销毁栈。

（4）Judge()函数是利用switch语句对传入进来的运算符进行判断，并将传入的两个数进行相应的运算，并返回运算结果。

二、算法流程图

算法一：

利用栈将中缀表达式转化成后缀表达式再进行计算。

图1为算法一中main()函数的算法流程图，主要功能为：录入字符串和区分数字字符与运算符字符。

图1 中缀转后缀表达式算法main()函数流程图

图2为算法一中Mid_Back()函数的算法流程图，主要功能为：将中缀表达式转换

成后缀表达式。

图2中缀转后缀表达式算法Mid_Back()函数流程图

图3为算法一中countfor()函数的算法流程图，主要功能为：根据后缀表达式求出表达式的值。

图3中缀转后缀表达式算法countfor()函数流程图

算法二：

利用两个栈（数字栈和符号栈）直接对表达式求值。

图4为算法二中main()函数的算法流程图，主要功能为：录入字符串和区分数字字符与运算符字符。

图4表达式直接求值算法main()函数流程图

图5为算法二中Countfor ()函数的算法流程图，主要功能为：利用两个栈直接对表达式进行取值计算。

利用栈实现c语言计算器

栈的应用：C实现简单计算器（表达式的计算） 作为栈的著名应用，表达式的计算可以用下面方法实现： 首先建立两个栈，操作数栈NUM_S和运算符栈OPR_S。 其中，操作数栈用来存储表达式中的操作数；运算符栈用来存储表达式中的运算符。可以用字符‘=’来表示表达式结束符。 自左至右的扫描待处理的表达式，并假设当前扫描到的符号为W，根据不同的符号W 做如下不同的处理： 1.若W为操作数，则将W压入操作数栈NUM_S，且继续扫描下一个字符； 2.若W为运算符，则根据运算符的性质做相应的处理： （0）若符号栈为空，无条件入栈当前指针指向的字符 （1）若w为不大于运算符栈栈顶的运算符，则从操作数栈NUM_S中弹出两个操作数，设先后弹出的操作数为a、b，再从运算符栈 OPR_S中弹出一个运算符，比如为+，然后作运算a+b,并将运算结果压入操作数栈NUM_S。 （2）若w为左括号或者运算符的优先级大于运算符栈栈顶的运算符，则将运算符W 压入运算符栈OPR_S，并继续扫描下一个字符。 （3）若运算符W为右括号，循环操作（设先后弹出的操作数为a、b，再从运算符栈OPR_S中弹出一个运算符，比如为+，然后作运 算a+b, 并将运算结果压入操作数栈NUM_S），直到从运算符栈中弹出第一个左括号。 （4）若运算符W为表达式结束符‘=’，循环操作（设先后弹出的操作数为a、b，再从运算符栈OPR_S中弹出一个运算符，比如为 +，然后作运算a+b, 并将运算结果压入操作数栈NUM_S），直到运算符栈为空为止。此时，操作数栈栈顶元素即为表达式的 值。 ====================================================================== === 举例：计算3+(5-2*3)/4-2= （1）开始栈为空，3入栈，+入栈，（无条件入栈，5入栈，-号优先级比（高，所以-号入栈，2入栈，*优先级比目前栈顶的-号优先级高，所以*入栈，3入栈，接着扫描到）括号，）括号不入栈 | | | | --------- ---------- | 3 | | * | --------- ---------- | 2 | | - |

数据结构算术表达式求值实验报告

软件技术基础实验报告 实验名称：表达式计算器 系别：通信工程 年级： 班级： 学生学号： 学生姓名： 《数据结构》课程设计报告 题目简易计算表达式的演示 【题目要求】 要求：实现基本表达式计算的功能 输入：数学表达式，表达式由整数和“+”、“-”、“×”、“/”、“（”、“）”组成输出：表达式的值 基本操作：键入表达式，开始计算，计算过程和结果记录在文档中 难点：括号的处理、乘除的优先级高于加减

1．前言 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。 算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为+、-*、/、=，用#表示结束。 算法输出：表达式运算结果。 算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。 2．概要设计 2.1 数据结构设计 任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top 指示栈顶元素在顺序栈中的位置，base 为栈底指针，在顺序栈中，它始终指向栈底，即top=base 可作为栈空的标记，每当插入新的栈顶元素时，指针top 增1，删除栈顶元素时，指针top 减1。 2.2 算法设计 为了实现算符优先算法。可以使用两个工作栈。一个称为OPTR ，用以寄存运算符，另一个称做OPND ，用以寄存操作数或运算结果。 1.首先置操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素； 2.依次读入表达式，若是操作符即进OPND 栈，若是运算符则和OPTR 栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即OPTR 栈的栈顶元素和当前读入的字符均为”#”）。 2.3 ADT 描述 ADT Stack{ 数据对象：D={ i a |i a ∈ElemSet,i=1,2,…，n, n ≧0} 数据对象：R1={< 1 ,-i i a a >| 1-i a ,D a i ∈,i=2,…，n}

表达式求值算法实现

湖南人文科技学院计算机科学技术系 课程设计说明书 课程名称:数据结构 课程代码:408024 题目: 表达式求值 年级/专业/班:08级计算机科学与技术二班 学生姓名: 黄胜李业芝黄自强 黄沅涛姚洋 学号:08408210 08408211 08408212

08408213 08408215 指导教师: 袁辉勇 开题时间: 2009 年12 月21 日 完成时间: 2010 年 1 月 1 日

目录 摘要 (1) 一、引言 (3) 二、设计目的与任务 (3) 1、课程设计目的 (3) 2、课程设计的任务 (4) 三、设计方案 (4) 1、需求分析 (4) 2、概要设计 (4) 3、详细设计 (6) 4、程序清单 (13) 四、调试分析与体会 (17) 五、运行结果 (18) 六、结论 (20) 七、致谢 (21) 八、参考文献 (21)

摘要 在高级语言环境中算术表达上的结果是通过语言环境预设的算法的思想计算出来的，然而高级语言初学者并不了解表达式的计算过程和方法。本文采用算符优先分析和堆栈的方法给出了算术表达式的计算过程。 所以本次课程设计的程序是在Windows系统上为用户解决包括加、减、乘、除以及括号在内的四则混合运算。用户可通过键盘输入四则运算，经过程序运行之后，可以判断出用户所输入的表达式是否正确。如果正确，就给出表达式的值；如果不正确，就提示输入有误。 关键词：四则混合运算；高级语言；栈 Abstract The arithmetic expression result is the algorithm thought which supposes in advance through the language environment calculatesin the higher order language environment,however the higher order language beginner does not understand the expression the computationprocess and the method. This article used the operator first to analyze and the storehouse method has given the arithmetic expression computa-tion process. Therefore, the procedure in this curriculum design is the solution for users on Windows systems, including add, subtract, multiply, divide and brackets, including four hybrid operation. Users can enter via the keyboard 4 operation, after a program is running, you can determine the user entered expression is correct. If correct, it gives the value of the expression; if not correct, it prompted an error.

栈的应用表达式求值的设计

数据结构课程设计报告 栈的应用：表达式求值 专业 计算机科学与技术 学生姓名 班级 学 号 指导教师 完成日期 2014年7月4日

表达式求值的设计 目录 1设计内容 (1) 2设计分析 (1) 2.1后缀表达式设计 (1) 2.2 中缀到后缀的转换设计 (2) 3设计实践 (3) 3.1实现要求 (3) 3.2程序代码 (3) 4测试方法 (17) 4.1测试目的 (17) 4.2 测试输入 (17) 4.3 正确输出 (18) 4.4 实际输出 (18) 5程序运行效果 (18) 6设计心得 (19)

栈的应用：表达式求值的设计 1设计内容 设计一个表达式求值的程序。该程序必须可以接受包含(,),+,-,*,/,%,和^（求幂运算符，a^b=a b）的中缀表达式，并求出结果。如果表达式正确，则输出表达式的结果；如果表达式非法，则输出错误信息。 输入要求：程序从“input.txt”文件中读取信息，在这个文件中如果有多个中缀表达式，则每个表达式独占一行，程序的读取操作在文件在文件的结尾处停止。 输出要求：对于每个表达式，将其结果放在“output.txt”文件的每一行中。这些结果可能是值，也可能是错误信息“ERROR IN INFIX NOTATION”。 2 设计分析 在计算机中，算术表达式的计算往往是通过使用栈来实现的。所以，本表达式求值程序的最主要的数据结构就是栈。可以使用栈来存储输入表达式的操作符和操作数。 输入的表达式是由操作数（又称运算对象）和运算符以及改变运算次序的圆括号连接而成的式子。算术表达式有中缀表示法和后缀表示法，本程序输入的表达式采用中缀表示法，在这种表达式中，二元运算符位于两个操作数中间。 由于不同运算符之间存在优先级，同一优先级的运算间又存在着运算结合顺序的问题，所以简单的从左到右的计算是不充分的。当然凭直观判断一个中缀表达式中哪个运算符最先，哪个次之，哪个最后并不困难，但通过计算机处理就比较困难了。因为计算机只能一个字符一个字符地扫描，要想知道哪个运算符先算，就必须对整个中缀表达式扫描一遍。 而后缀表达式则很容易通过应用栈实现表达式的计算，这为实现表达式求值程序提供了一种直接的计算机制。 2.1后缀表达式设计 后缀表达式是由一系列的运算符、操作数组成的表达式，其中运算符位于两个操作数之后。后缀表达式很容易通过应用栈实现表达式的计算。其基本过程是：当输入一个操作数时，它被压入栈中，当一个运算符出现时，就从栈中弹出适当数量的操作数，对该运算进行计算，计算结果再压回栈中。对于最常见的二元运算符来说，弹出的操作数只有两个。处理完整个后缀表达式之后，栈顶上的元素就是表达式的结果值。整个计算过程不需要理解计算的优先级规则。

实验2 栈和队列的应用-算术表达式求值

1.实验题目 栈和队列的应用 2.实验内容 算术表达式求值 3.实验目的 掌握栈和队列的概念及工作原理，运用其原理完成实验题目中的内容。 4.实验要求 为了更好的掌握与理解课堂上老师所讲的概念与原理，实验前要认真预习所做的实验内容及编写源程序伪码（写在纸上及盘中均可）以便在实验课中完成老师所布置的实验内容。 5.概要设计原理 6.详细程序清单及注释说明 #include #include #include #include #define NULL 0 #define OK 1 #define OVERFLOW -2 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 20 /* 定义字符类型栈*/ typedef struct { int stacksize; char *base; char *top; }SqStack; /* ----------------- 全局变量--------------- */ SqStack OPTR,OPND;// 定义运算符栈和操作数栈 char expr[255]; /* 存放表达式串*/ char *ptr=expr; int InitStack(SqStack *s) //构造运算符栈 { s->base=(char *)malloc(STACK_INIT_SIZE*sizeof(char)); if(!s->base) exit(OVERFLOW);

s->top=s->base; s->stacksize=STACK_INIT_SIZE; return OK; } char In(char ch) //判断字符是否是运算符，运算符即返回1 { return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#'); } int Push(SqStack *s,char ch) //运算符栈插入ch为新的栈顶元素{ *s->top=ch; s->top++; return 0; } char Pop(SqStack *s) //删除运算符栈s的栈顶元素，用p返回其值{ char p; s->top--; p=*s->top; return p; } char GetTop(SqStack s)//用p返回运算符栈s的栈顶元素 { char p=*(s.top-1); return p; } /* 判断运算符优先权，返回优先权高的*/ char Precede(char c1,char c2) { int i=0,j=0; static char array[49]={ '>', '>', '<', '<', '<', '>', '>', '>', '>', '<', '<', '<', '>', '>', '>', '>', '>', '>', '<', '>', '>', '>', '>', '>', '>', '<', '>', '>', '<', '<', '<', '<', '<', '=', '!', '>', '>', '>', '>', '!', '>', '>', '<', '<', '<', '<', '<', '!', '='};

利用栈求表达式的值,可供小学生作业,并能给出分数 数据结构课程设计说明书格式

中北大学 数据结构 课程设计说明书 2011年12月20日

1. 设计任务概述（包括系统总体框图及功能描述） 此课题是研究表达式求值的问题，以帮助小学生完成测试。为了达到这个功能，实际我们要做的就是出题，和计算分数给出评价的工作。整体设计都是以这个要求为轴心进行的。为了直观和方便，现画出软件整体设计模块图。 整体设计模块图可以清晰的看出软件的几大模块。整个系统的操作流程图可以看出操作的整体流程，如下图 2.

根据以上功能说明，设计运算信息，堆栈的存储结构，设计程序完成功能； 3. 功能模块详细设计 在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义）。 3.1 详细设计思想 学生要进行测试，首先要有试题。那么我们就要先建立试题库。这个试题库的试题是我们在程序运行过程中手动输入，存放在一个shujuku.txt的文件中。 首先在主函数中调用创建试题库函数，将试题存入到试题库文件shitiku.txt中，然后将该调用从主函数中删除。 创建试题库函数：创建指向xuanti类型的指针，利用循环将输入的测试题该指针的xuanti单元中，最后将该指针中的测试题写入试题库文件shitiku.txt中。 3.2 核心代码 (正文宋体小四号字，1.5倍行距) #include #include #include #include #include #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define ERROR 0 #define OK 1 //定义表达式

(完整版)数学表达式计算(c语言实现)

一、设计思想 计算算术表达式可以用两种方法实现： 1.中缀转后缀算法 此算法分两步实现：先将算术表达式转换为后缀表达式，然后对后缀表达式进行计算。具体实现方法如下： （1）中缀转后缀 需要建一个操作符栈op和一个字符数组exp，op栈存放操作符，字符数组用来存放转换以后的后缀表达式。首先，得到用户输入的中缀表达式，将其存入str数组中。 对str数组逐个扫描，如果是数字或小数点，则直接存入exp数组中，当扫描完数值后，在后面加一个#作为分隔符。 如果是操作符，并且栈为空直接入栈，如果栈不为空，与栈顶操作符比较优先等级，若比栈顶优先级高，入栈；如果比栈顶优先级低或相等，出栈将其操作符存到exp数组中，直到栈顶元素优先等级低于扫描的操作符，则此操作符入栈；如果是左括号，直接入栈，如果是右括号，出栈存入exp数组，直到遇到左括号，左括号丢掉。然后继续扫描下一个字符，直到遇到str中的结束符号\0，扫描结束。结束后看op栈是否为空，若不为空，继续出栈存入exp数组中，直到栈为空。到此在exp数组最后加结束字符\0。 我们就得到了后缀表达式。 （2）后缀表达式计算 此时需要一个数值栈od来存放数值。对exp数组进行逐个扫描，当遇到数字或小数点时，截取数值子串将其转换成double类型的小数，存入od栈中。当遇到操作符，从栈中取出两个数，进行计算后再放入栈中。继续扫描，知道扫描结束，此时值栈中的数值就是计算的结果，取出返回计算结果。 2.两个栈实现算法 此算法需要两个栈，一个值栈od，一个操作符栈op。将用户输入的数学表达式存入str数组中，对其数组进行逐个扫描。 当遇到数字或小数点，截取数值子串，将其转换成double类型的数值存入od栈中； 当遇到左括号，直接入op栈；遇到右括号，op栈出栈，再从值栈od中取出两个数值，计算将其结果存入值栈中，一直进行此操作，直到操作符栈栈顶为左括号，将左括号丢掉。 如果遇到操作符，若op栈为空，直接入栈；若栈不为空，与栈顶元素比较优先等级，若比栈顶操作符优先等级高，直接入op栈，如果低于或等于栈顶优先等级，op栈出栈，再从值栈中取出两个数值，计算将其结果存入值栈中，一直进行此操作，直到栈顶优先等级低于扫描的操作符等级，将此操作符入op栈。继续扫描直到遇到str中的结束字符\0，扫描结束。此时看操作符栈是否为空，若不为空，出栈，再从值栈中取出两个数值进行计算，将其结果存入值栈，一直进行此操作，直到操作符栈为空。此时把值栈中的数值取出，即为所得的最终计算结果。 二、算法流程图 第一种算法：中缀转后缀算法

利用栈求表达式的值

数据结构课程设计 姓名：杨颂敬 班级：软件0901班 学号：0930*******

目录： 1．需求分析 (1) 2．概要设计 (1) 3．详细设计................................. 3-6 4．调试分析................................. 6-8 5．用户使用说明 (8) 6．测试结果 (9) 7．附录 (9)

利用栈求表达式的值，可供小学生作业，并 能给出分数。 1．需求分析 任务：通过此系统可以实现如下功能： 此系统能够输入一个表达式，并计算该表达式的值。可以根据计算结果给出分数。能供小学生进行简单的四则运算，此外这里特别强调括号的匹配！ 要求： 根据以上功能说明，设计运算信息，堆栈的存储结构，设计程序 完成功能； 2. 概要设计 在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义）。 主菜单

3．详细设计 #include "string.h" #include "stdio.h" #include"conio.h" #define maxsize 100 #include "ctype.h" typedef char datatype; typedef struct { datatype stack[maxsize]; int top; } seqstack; void stackinitiate(seqstack *s) { s->top=0; } int stacknotempty(seqstack s) { if(s.top<=0) return 0; else return 1; } int stackpush(seqstack *s, datatype x) { if(s->top>=maxsize) { printf("堆栈已满无法插入!\n"); return 0; } else { s->stack[s->top]=x; s->top++; return 1; } } int stackpop(seqstack *s,datatype *d) { if(s->top<=0) {

基于栈结构的中缀表达式求值

实验3：栈与队列实验 ——基于栈结构的中缀表达式求值 一、问题描述 从键盘输入任意中缀表达式字符串，读字符串，利用栈结构实现表达式求值。 二、输入与输出 输入：从键盘中缀表达式如： 32＋5×（6－4） 输出：计算结果42 三、需求分析 1.定义两个栈结构，数栈用于存放表达式中的数，符号栈用于存放表达式中的符号，实现栈的运算 2.在读数的时候考虑多位运算 3.实现表达式求值 四、开发工具与环境 硬件设备：微型计算机系统 软件环境：操作系统Windows 开发工具：Devc++ 五、概要设计 参考结构定义 typedef struct /* 运算符栈 */ { char *base,*top; int stacksize; }SqStack; typedef struct /* 运算数栈 */ { int *base,*top; int stacksize; }SqStack1; int priority[7][7]={{'>', '>', '<', '<', '<', '>', '>'}, // + {'>', '>', '<', '<', '<', '>', '>'}, // -

{'>', '>', '>', '>', '<', '>', '>'}, // * {'>', '>', '>', '>', '<', '>', '>'}, // / {'<', '<', '<', '<', '<', '=', ' '}, // ( {'>', '>', '>', '>', ' ', '>', '>'}, // ) {'<', '<', '<', '<', '<', ' ', '='} // # }; /*用于比较符号优先级的全局二维数组*/ 2．各函数模块 void InitStack(SqStack *s); 操作结果：初始化运算符栈 char GetTop(SqStack *s); 操作结果：得到运算符栈的栈顶元素 void Push(SqStack *s,char e); 操作结果：对运算符栈进行压栈操作 int IsNumber(char c); 操作结果：判断一个字符是否是数字 int MidExpression_Eval(char Express[]); 操作结果：计算中缀表达式的值 int Operate (int a,char x,int b); 操作结果：计算表达式axb，并返回结果 六、详细设计 #include #include using namespace std; /*定义区*/ #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OVERFLOW -1 #define ERROR 0 #define OK 1 //运算符栈 typedef struct { char *base, *top; int stacksize; }SqStack; //运算数栈 typedef struct { int *base, *top; int stacksize;

带括号的四则运算表达式的求值栈实现

带括号的四则运算表达式的求值（栈实现） 利用栈这种数据结构来实现一个加减乘除以及带括弧的混合数学表达式的计算，对于数学表达式的计算，可以设置一个运算符栈和一个数字栈，分别来保存运算符、数字或者中间计算得到的结果。将整个表达式看做一个字符串，从开头依次判断每个字符是运算符还是数字，若是运算符，则根据运算符优先级来确定是将其压栈还是弹栈进行计算；若是数字，则先将其转化并计入一个临时double型变量中，看下一个字符是否为运算符栈，若是，则将临时变量压进数字栈，否则读取下一个数字字符并进行相关处理后累加到临时变量中，直到下一个字符为运算符，将临时变量压进数字栈。最后，当字符为"="时，结束计算，得到计算结果。本算法需要先设置一个运算符优先级表，下表可供参考： +-*/()= +>><<<>> ->><<<>> *>>>><>> />>>><>> (<<<<<= )>>>>?>> =<<<<

while(!IsOper(s[j])) { { point = 10; j++; continue; } if(!point)? 5 - 7 / 2 + 3. - .1 1 + 2 / ( 2 - / ) - 3 2 * ( ( 3 + 2 ) - 3 */ 本代码生成的程序，在输入表达式时，数字与运算符之间可以有若干空格或者没有；对于小数，可以没有整数部分（即小数点之前没有数字），也可以没有小数部分（即小数点之后没有数字）；表达式可以为无效表达式（如括号不匹配或者出现除数为0的情况等）；如以上的样例输入。对于以上样例输入，其对应输出结果为： The divisor cannot be zero! The parentheses do not match!

利用栈求表达式的值,可供小学生作业,并能给出分数

//1.h #include #include #include #include #include using namespace std; //template struct Ti //定义一个结构体，用于存储题习题库中的每一道台?题目 { char chh[30]; }; template struct Stack //定义栈，其中数据元素为字符型í { T data[50]; int top; }; template struct Stack2 //定义栈，其中数据元素为整型í { float data[50]; int top; }; template

class link { public: void Push(Stack &S,char x); char Pop(Stack &S,char x); void Push2(Stack2 &S,float x); float Pop2(Stack2 &S,float x); void pingjia(int m) ; int In(char c); int change(char x); int Precede(int a,int b); float Operate(float a,char c,float b); void toEmpty(char s[],int n); void isStay(char s1[],int n1,char s2[],int n2); int isInt(char s[],int n); void xitiku(char a[],int n); float Expression(); Stack setStack(); Stack2 setStack2(); }; //1.cpp #include #include"1.h" #include #include #include #include

c语言实现一.二叉树操作 二.用栈实现算术表达式求值 课设报告

目录 题目一.二叉树操作（1）二.算术表达式求 (1) 一、课程设计的目的 (1) 二、课程设计的内容和要求 (1) 三、题目一设计过程 (2) 四、题目二设计过程 (6) 五、设计总结 (17) 六、参考文献 (18)

题目一.二叉树操作（1）二.算术表达式求 一、课程设计的目的 本学期我们对《数据结构》这门课程进行了学习。这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。这次课程设计不但要求学生掌握《数据结构》中的各方面知识，还要求学生具备一定的C语言基础和编程能力。 （1）题目一的目的： 1、掌握二叉树的概念和性质 2、掌握二叉树的存储结构 3、掌握二叉树的基本操作 （2）题目二的目的： 1、掌握栈的顺序存储结构和链式存储结构 2、掌握栈的先进后出的特点 3、掌握栈的基本运算 二、课程设计的内容和要求 （1）题目一的内容和要求： 1、编写已知二叉树的先序、中序序列，恢复此二叉树的程序 2、编写求二叉树深度的程序 （2）题目二的内容和要求： 1、算术表达式由操作数、运算符和界限符组成。操作数是正整数，运算符为 加减乘除，界限符有左右括号和表达式起始 2、将一个表达式的中缀形式转化为相应的后缀形式 3、依据后缀表达式计算表达式的值

三、题目一设计过程 1、题目分析 现已知一棵二叉树的先序遍历序列和中序遍历序列，依次从先序遍历序列中取结点，由先序序列确定根结点(就是第一个字母)，每次取出一个结点就与中序遍历的序列进行比较，当相等的时候，中序遍历序列就被分成以该结点为根的二叉树子树，该结点左部分为左子树，右部分为右子树，直到取完先序列里的所有结点，则二叉树构造完毕（树用链式存储结构存储），用递归实现！ 由建好的二叉树，先判断这棵树是否为空，若不为空则找数的左子树，统计它的高度，然后找树的右子树，统计它的高度，比较左子树和右子树的高度，然后返回其中大的那个值加一，则求出数的高度。这里用递归实现！ 2、算法描述 main ( )（主函数） 先构造一颗二叉树，初始化为空，用来存储所构造的二叉树，并输入一棵树的先序序列和中序序列，并统计这个序列的长度。然后调用实现功能的函数。 void CreateBiTree(BiTree *T,char *pre,char *in,int len)（由先序序列和中序序列构造二叉树） 根据前序遍历的特点, 知前序序列(pre)的首个元素(pre[0])为根(root), 然后在中序序列(in)中查找此根(pre[0]), 根据中序遍历特点, 知在查找到的根(root) 前边的序列为左子树, 后边的序列为右子树。设根前边有n个元素，则又有, 在前序序列中，紧跟着根(root)的n个元素序列(即pre[1...n]) 为左子树, 在后边的为右子树，而构造左子树问题其实跟构造整个二叉树问题一样，只是此时前序序列为pre[1...n]), 中序序列为in[0...n-1], 分别为原序列的子串, 构造右子树同样。这里用递归实现！ int Depth(BiTree T)（求树的深度） 当所给的参数T是NULL时，返回0。说明这个树只有一个叶子节点深度为0，当所给的参数不是NULL时，函数调用自己看看这个参数的左分支是不是NULL，

利用栈实现多项式的计算,

/*************************** //利用栈实现多项式的计算， //如输入: 3*(7-2)# //输出：3*(7-2)#=15 //清华大学——数据结构——53页 ****************************/ // v4.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include #include #include #define STACK_INIT_SIZE 100 //定义初始栈的大小#define Status bool /*************************** //定义栈元素的结构 ****************************/ typedef char ElemType; typedefstruct { ElemType * base; ElemType * top; intstacksize; } Stack; /*************************** //栈的初始化 ****************************/ voidInitStack( Stack & s) { s.base = ( ElemType *) malloc ( STACK_INIT_SIZE ); s.top = s.base; s.stacksize = STACK_INIT_SIZE; }

/*************************** //取栈顶元素 ****************************/ ElemTypeGetTop(Stack s) { return ( *(s.top - 1)); } /*************************** //压栈 ****************************/ void Push(Stack &s, ElemType e) { * s.top ++ = e; } /*************************** //弹栈 ****************************/ void Pop(Stack &s, ElemType& e) { e = * -- s.top; } #define OPSETSIZE 7 unsigned char prior[7][7] = { '>','>','<','<','<','>','>', '>','>','<','<','<','>','>', '>','>','>','>','<','>','>', '>','>','>','>','<','>','>', '<','<','<','<','<','=',' ', '>','>','>','>',' ','>','>', '<','<','<','<','<',' ','=' }; char OPSET1[7] = {'+', '-' , '*' , '/' ,'(' , ')' , '#'}; /******************************************************

实验四 栈的应用---算术表达式的计算

浙江大学城市学院实验报告 课程名称数据结构与算法 实验项目名称实验四栈的应用---算术表达式的计算 学生姓名专业班级学号 实验成绩指导老师（签名）日期 一.实验目的和要求 1．进一步掌握栈的基本操作的实现。 2．掌握栈在算术表达式的计算方面的应用。 二. 实验内容 1.编写程序对后缀表达式进行求值（利用栈），即从键盘输入任一个后缀表达式，输出该后缀表达式的值。要求：把栈的基本操作的实现函数存放在文件stack.h中，在主程序文件test4.cpp中包含后缀表达式求值函数double Compute(char *str)与主函数。 2．填写实验报告，实验报告文件取名为report4.doc。 3．上传实验报告文件report4.doc与源程序文件stack.h及test4.cpp到Ftp服务器上你自己的文件夹下。 三. 函数的功能说明及算法思路 包括每个函数的功能说明，及一些重要函数的算法实现思路 四. 实验结果与分析 包括运行结果截图等

五. 心得体会 记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。 看着书写，问题不大。自己写可能会漏写一些情况。 【附录----源程序】 Test4.cpp #include #include #include"stack.h" double Compute(char *str){ Stack S; InitStack(S); double x,y; int i = 0; while(str[i]){ if(str[i] == ' '){ i++; continue; } switch(str[i]){ case'+': x = Pop(S) + Pop(S); i++; break; case'-': x = Pop(S);

四则运算表达式求值(栈+二叉树,c++版)

HUNAN UNIVERSITY 课程实习报告 题目：四则运算表达式求值 学生姓名：周华毅 学生学号：201308010411 专业班级：计科1304 指导老师：吴帆 完成日期：2015/5/1

一、需求分析 a)四则运算表达式求值，将四则运算表达式用中缀表达式表示，然后转换为后缀表达 式，并计算结果。 b)本程序要求利用二叉树后序遍历来实现表达式的转换，同时可以使用实验2的结 果来求解后缀表达式的值。 c)在字符界面上输入一个中缀表达式，回车表示结束。如果该中缀表达式正确，那么 在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔 开；如果不正确，在字符界面上输出表达式错误提示。 d)测试数据 输入： 21+23*（12-6） 输出： 21 23 12 6 -*+ 二、概要设计 抽象数据类型 为实现上述程序的功能，应以字符串存储用户的输入，以及计算出的结果。 算法的基本思想 根据题目要求，利用二叉树后序遍历来实现表达式的转换。该算法的基本模块包括二叉树的建立以及如何把输入的中缀表达式利用二叉树后序遍历转化为后缀表达式。 1、首先要将输入的中缀表达式（数字字符）存入到二叉树中，由于存在两位或者两位以上的数，甚至还有小数，所以考虑用字符型指针存储数字字符和操作符。 2、为了便于将中缀表达式存入二叉树中，在录入中缀表达式后，要进行相应的处理，比如去掉空格符，添加结束标志，如‘=’、‘#’等。 3、中缀表达式存入到二叉树的过程中，要注意处理的顺序，如‘+’、‘-’号的优先级比‘*’、‘/’号的低，当遇到‘*’、‘/’号时，要判断树以上的节点中是否有‘+’、‘-’号，有的话要与其交换位置。遇到‘（’时要反复创建二叉树的结点，构建子二叉树，考虑到括号内要处理的步骤可能会较多，可以考虑用递归。遇到‘）’时则直接结束此子二叉树的建立。此外二叉树中叶子结点存储操作数，非叶子结点存储操作码。 4、对创建好的二叉树进行后序遍历，即可得到相应的后缀表达式，实现方法可以用递归的方式，由于后面还要计算表达式的值，故便利的过程中要将结点中得到的数据存入新的字符数组中。 程序的流程 程序由三个模块组成： （1）输入模块：完成一个中缀表达式的输入，存入字符串数组array[Max]中。 （2）计算模块：设计一个建立二叉树的函数，Node* crtTree(Node* root)，传入根结点指针，返回根结点指针，该函数的实现还要反复使用另一个函数char getOp(Node *temp)，其将数字字符存入一个结点，并返回数字字符的后一 个符号。void deal()函数功能是对字符数组进行处理。void output(Node *root); 函数功能是获得处理后的字符串，也就是中缀表达式转化为的后 缀表达式。 （3）输出模块：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式和表达式的值；如果不正确，在字符界面上输出表达式错误提示。 三、详细设计

用两种方法实现表达式求值

一、设计思想 一．中缀式计算结果的设计思想： 此种算法最主要是用了两个栈：用两个栈来实现算符优先，一个栈用来保存需要计算的数据numStack（操作数栈）,一个用来保存计算优先符priStack（操作符栈）。从字符串中获取元素，如果是操作数，则直接进操作数栈，但如果获取的是操作符，则要分情况讨论，如下：（这里讨论优先级时暂不包括“（”和“）”的优先级） 1.如果获取的操作符a的优先级高于操作符栈栈顶元素b的优先级，则a直接入操作符栈; 2.如果获取的操作符a的优先级低于操作符栈栈顶元素b的优先级，则b出栈，a进栈，并且取出操作数栈的栈顶元素m，再取出操作数栈新的栈顶元素n，如果b为+，则用n+m，若为减号，则n-m，依此类推，并将所得结果入操作数栈； 3.如果获取的是“（”，则直接进操作符栈； 4.如果获取的是“）”，则操作符栈的栈顶元素出栈,做类似于情况2的计算，之后把计算结果入操作数栈，再取操作符栈顶元素，如果不是“（”，则出栈，重复操作，直到操作符栈顶元素为“（”，然后“（”出栈； 5.当表达式中的所有元素都入栈后，看操作符栈中是否还有元素，如果有，则做类似于情况2 的计算，并将结果存入操作数栈，则操作数栈中最终的栈顶元素就是所要求的结果。 二．中缀转后缀及对后缀表达式计算的设计思想： 中缀转后缀时主要用了一个操作符栈和一个用来存放后缀表达式的栈，从表达式中依次获取元素，如果获取的是操作数，则直接存入s3栈中，如果获取的是操作符也需分情况讨论，如下：（这里讨论优先级时暂不包括“（”和“）”的优先级） 1. 如果获取的操作符a的优先级高于操作符栈栈顶元素b的优先级，则a直接入操作符栈; 2. 如果获取的操作符a的优先级低于操作符栈栈顶元素b的优先级，则b出栈，a进栈，并且将b存入到操作符栈中； 3.如果获取的是“（”，则直接进操作符栈； 4.如果获取的是“）”，则操作符栈的栈顶元素出栈,并依次存入到操作符栈中，直到操作符栈栈顶元素为“（”，然后将“（”出栈； 5.当表达式中的所有元素都入栈或存入到操作符栈之后，看操作符栈中是否还有元素，如果有，则依次出栈，并且依次存入到操作符栈中，最后打印操作符栈中的字符串，则此字符串即为要求的后缀表达式。 对后缀表达式的计算方法：主要用到了一个操作数栈，从操作符栈中依次取出元素，如果是操作数，则进栈，如果是操作符，则从操作数栈中依次取出两个栈顶元素a1和a2,如果操作符是“/”,则计算a2/a1,将计算结果再次进栈，依此类推，最终栈顶元素即为计算的最终结果。 在这两种算法中，应该特别注意一点：人的习惯，用户在输入表达式时，容易这样输入，如：3*4（3+2），这样是不可取的，应必须要用户输入3*4*（3+2），这是在设计思想上错误提示的很重要一点，否则计算不全面！ 二、算法流程图 第一个图是直接计算的流程图，图中反应除了这种方法的大致设计思路，但是有些细节没有反映出来，比如说，怎样把字符型数据转换为浮点型数据，就没有反映出来。特别说明