后缀表达式算法用栈对后缀表达式求值的算

表达式求值课程设计报告

表达式求值课程设计报告 表达式求值 《数据结构》 课程设计报告 题目: 栈的应用:表达式求值 (系): 信息科学与工程学院院 专业班级: 软件工程1102班学生姓名: 学号: 指导教师: 20 13 年 6 月 8 日至20 13 年 6 月 21 日 表达式求值 目录 目录 (2) 1 概述 (1) 1.1 课程设计目的 (1) 1.2 课程设计内容 (1) 2 系统需求分析 ...................................................... 1 2.1 系统目标 (1) 2.2 主体功能 (1) 2.3 开发环境 (1) 3 系统概要设计 .................................................... 2 3.1 系统的功能模块划分 (2)

3.2 系统流程图 (2) 4系统详细设计 ..................................................... 3 5 测试 ............................................................ 6 5.1 测试方案 (6) 5.2 测试结果 (6) 6 小结 ............................................................ 8 参考文献 .......................................................... 9 附录1 源程序清单 (10) 2 数据结构课程设计报告(2012) 表达式求值 1 概述 1.1 课程设计目的 1(要求学生达到熟练掌握C语言的基本知识和技能。 2(了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。 3(提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 4(培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提 高程序设计水平。

利用栈实现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 | | - |

后缀表达式求值

一、设计思想 首先，将中缀表达式转换为后缀表达式。转换算法思路：设中缀表达式已存入数组E[n]；由于后缀表达式中操作数的次序与中缀表达式一致，故扫描到中缀表达式操作数时直接输出到B[n]即可；对于运算符，视其优先级别，优先级高的运算符先输出；设一存放运算符的栈s，先将s置空；依次扫描E[n]中各分量E[i]送x： 若x=“”（结束符），依次输出栈s中运算符，转换结束； 若x=操作数，直接输出x到B[n]中； 若x=‘）’，反复退栈输出栈s中子表达式运算符，直到栈顶符=‘（’，并退掉栈顶的‘（’； 若x=操作符，反复退栈输出栈s中运算符，直到栈顶符

三、源代码 下面给出的是用后缀表达式求值算法实现的程序的源代码： #include #include #define MaxSize 50 struct { char data[MaxSize]; int top; } op;//定义栈； struct { float data[MaxSize]; int top; } st; //中缀转换为后缀 void trans(char*exp,char*postexp) { int i=0; op.top=-1; while(*exp!='\0') { switch(*exp) { case'(': op.top++;op.data[op.top]=*exp; exp++;break; case')': while(op.data[op.top]!='(') { postexp[i++]=op.data[op.top]; op.top--; } op.top--;exp++;break; case'+': case'-': while(op.top!=-1&&op.data[op.top]!='(') { postexp[i++]=op.data[op.top]; op.top--; }

数据结构课程设计_表达式求值问题

实验表达式求值问题 1.问题描述 表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*（7-4）/3.中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀表达式（如：11 22 7 4 - * 3 / +）和前缀表达式（+ 11 / * 22 - 7 4 3）。后缀表达式 和前缀表达式中没有括号，给计算带来方便。如后缀表达式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。 2.数据结构设计 （1）顺序栈类定义：首先应在类中定义成员函数，以此来完成顺序栈的相关操作，如下： class SqStack { private: T *base; //栈底指针 int top; //栈顶 int stacksize; //栈容量public: SqStack(int m); //构建函数 ~SqStack(){delete [] base;top=0;stacksize=0;} //析构函数 void Push(T x); //入栈 T Pop(); //出栈 T GetTop(); //获取栈顶元素

int StackEmpty(); //测栈空 void ClearStack(); //清空栈 void StackTop(); //返回栈顶指针 void StackTranverse(); //显示栈中元素 }; （2）顺序栈类实现：对顺序栈进行初始化，初始化的首要操作就是创建一个空顺序栈。 Step1：申请一组连续的存空间为顺序栈使用： base=new T[m]; i f(base==NULL) { cout<<"栈创建失败，退出!"<

(完整版)数学表达式计算(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，扫描结束。此时看操作符栈是否为空，若不为空，出栈，再从值栈中取出两个数值进行计算，将其结果存入值栈，一直进行此操作，直到操作符栈为空。此时把值栈中的数值取出，即为所得的最终计算结果。 二、算法流程图 第一种算法：中缀转后缀算法

C语言 后缀表达式计算

一、设计思想 计算算数表达式并求值，采取的共有两种方法： 1.先将算数表达式转化为后缀表达式，然后对后缀表达式进行计算。 2.对算数表达式进行直接的计算。 第一种算法 这种解决方案又分为两步： 1.将表达式先转化为后缀表达式的字符串数组 2.利用后缀表达式进行计算 在转化过程中，第一，建立一个存符号的栈，和一个字符串数组，用来存放转化以后的表达式 然后，对于得到的用户输入的字符串进行逐个的扫描，如果是数组或者小数点，则直接存放到数组中，并且在后面加入一个分隔符，如果是操作符，则和栈中的已存的进行比较，如果比栈中的操作符的优先级高，则直接入栈，如果优先级低或相等，则栈中元素出栈，存到字符串中，然后再次检查栈顶，直到栈中元素的优先级低于扫描操作符，则此操作符入栈，然后扫描下一个字符，直到遇到字符串的结束符号\0，扫描结束。数组中存的就是后缀表达式。得到后缀表达式后，进行计算，要用到数值栈。首先要将字符表示的数字转化为浮点小数，然后进行扫描，遇到数值，放入栈中，遇到操作符，就从栈中取出两个数，进行计算后再放入栈中，扫描下一个，最后的计算结果就存到了栈中，直接取出栈内元素，就是计算的最后结果。 第二种算发 首先要建立两个栈，一个用来存放操作符，一个用来存放数值。开始对用户输入的字符串进行扫描，如果是数字字符或者小数点，则将字符转化为浮点数存到数栈里，如果是操作符，则观察符号栈，如果栈顶元素的优先级低于观察的操作符，则操作符入栈，如果栈顶元素的优先级高于或者等于观察的操作符，则从数值栈中取出两个浮点数，从符号栈中取出栈顶的操作符，然后进行相应的数值计算，所得的结果再存到数值栈中，重复这样的操作，直到符号栈中栈顶元素的优先级低于观察的操作符，则此操作符入栈，然后对下一个字符进行扫描。如果是左括号，则不进行优先级的比较，直接入栈，入栈后优先级为-1。如果是右括号，则从数值栈中取两个操作数，符号栈中取出一个符号，然后进行计算后得数放入数栈中，不断进行此类操作，直到从栈中取出的是左括号为止，左括号去掉，扫描下一个。扫描结束后，计算也结束了，计算的结果就存放在数值栈中，最后把数值栈中的数取出，就是所得的计算结果。 容错的算法简要： 括号匹配：当扫描到左括号是，左括号直接入栈，扫描到右括号时，则左括号出栈，如果栈为空，则右括号多，如果最后栈中还有括号，则左括号多。给出错误提示。 除数不为0：当扫描到'/'时，就判断其后面的数字是否为0，如果为0报错。 取余运算：取余运算时，操作数判断是否为整数，不为整数报错。 二、算法流程图 第一种算法:先将表达式转化为后缀表达式，然后计算 其主函数流程图为：

后缀表达式求值的算法及代码

#include #include struct node // 栈结构声明 { int data; // 数据域 struct node *next; // 指针域 }; typedef struct node stacklist; // 链表类型 typedef stacklist *link; // 链表指针类型 link operand=NULL; // 操作数栈指针 link push(link stack,int value) // 进栈 { link newnode; // 新结点指针 newnode=new stacklist; // 分配新结点 if (!newnode) { printf("分配失败！"); return NULL; } newnode->data=value; // 创建结点的内容 newnode->next=stack; stack=newnode; // 新结点成为栈的开始return stack; } link pop(link stack,int *value) // 出栈 { link top; // 指向栈顶 if (stack !=NULL) { top=stack; // 指向栈顶 stack=stack->next; // 移动栈顶指针 *value=top->data; // 取数据 delete top; // 吸收结点 return stack; // 返回栈顶指针} else *value=-1; } int empty(link stack) // 判栈空 { if (stack!=NULL)

表达式求值程序设计说明书

汇编语言实训课程设计任务书 题目：表达式求值程序班级：计算机科学与技术一班 学生姓名：赵旭尧学号： 14730141 题目类型：软件工程（R）指导教师：刘树群 一．题目简介 该设计要求学生使用汇编语言，设计并开发出针对四则运算表达式进行求 值的命令行或窗口程序。 通过该题目的设计过程，可以培养学生结构化程序设计的思想，加深对汇 编语言基本语言要素和流程结构的理解，针对汇编语言中的重点和难点内容进 行训练，独立完成有一定工作量的程序设计任务，同时强调好的程序设计风格。 得到软件工程的综合训练，提高解决实际问题的能力。 二．设计任务 1、查阅文献资料，一般在5篇以上； 2、通过键盘输入表达式，进行针对整数的“加减乘除”四则运算表达式 进行求值，有良好的界面； 3、完成软件结构设计和算法设计； 4、完成系统的软件开发和测试工作； 5、撰写设计说明书； 6、做好答辩工作。 三．主要内容、功能及技术指标 1、实现功能及指标：①使用Win32的窗口程序模式，实现表达式求值程序 及测试界面程序的设计与开发；②支持整数的四则运算、位运算和小括号等； ③使用文本框对表达式进行交互式编辑和输出。 2、问题分析及解决方案框架确定：充分地分析和理解问题本身，弄清要求 做什么。在确定解决方案框架过程中，综合考虑系统功能，考虑怎样使系统结 构清晰、合理、简单和易于调试。最后确定每个过程和函数的简单功能，以及 过程（或函数）之间的调用关系，并画出函数之间的调用关系图。 3、详细设计和编码：定义相应的存储结构，确定各个函数的算法，并画出 流程图，在此基础上进行代码设计，每个明确的功能模块程序一般不超过200 行，否则要进一步划分。

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

中北大学 数据结构 课程设计说明书 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 //定义表达式

后缀表达式转化为前缀表达式并求值

#include #include #include #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OK 1 #define OVERFLOW -2 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Selemtype; typedef int Status; #define MAX 50 char string1[MAX]; //定义两个字符串分别存放中缀表达式和后缀表达式char string2[MAX]; int result; typedef struct { Selemtype *base; //在构造之前和销毁之后，base的值为NULL Selemtype *top; //栈顶指针 int stacksize; //当前分配的存储空间，以元素为单位 }SqStack; Status InitStack(SqStack *S); Status Push(SqStack *S,Selemtype e); Status Pop(SqStack *S,Selemtype e); Status InitStack(SqStack *S) { //构造一个空栈S S->base=(Selemtype*)malloc(STACK_INIT_SIZE*sizeof(Selemtype)); if(!S->base) return OVERFLOW; //存储分配失败 S->top=S->base; S->stacksize=STACK_INIT_SIZE; return OK; } Status Push(SqStack *S,Selemtype e) { //插入元素e为新的栈顶元素 if(S->top-S->base>=S->stacksize)

利用栈求表达式的值

数据结构课程设计 姓名：杨颂敬 班级：软件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) {

数据结构计算器(包括中缀转换后缀)课程设计报告

课程设计报告 题目：计算表达式的值 1.问题描述 对于给定的一个表达式，表达式中可以包括常数、算术运行符（“+”、“-”、“*”、“/”）和括号，编写程序计算表达式的值。 基本要求：从键盘输入一个正确的中缀表达式，将中缀表达式转换为对应的后缀表达式，并计算后缀表达式的值。对于表达式中的简单错误，能够给出提示，并给出错误信息；表达式中可以包括单个字母表示的变量。 测试数据：任意选取一个符合题目要求的表达式。 提高要求：（1）能够处理多种操作符。 （2）实现包含简单运算的计算器。 （3）实现一个包含简单运算和函数运算的计算器。 2.需求分析 （1）软件的基本功能 本软件实在win32工程下实现的带有界面和图标的功能较为齐全的计算器。 此计算器分三个方面进行计算，分别为数值表达式的计算，字母表达式的计算和函数计算。可由键盘或用鼠标点击按键输入带有数字或字母的中缀表达式，程序可以将输入的带有数字或字母的中缀表达式转换成对应的后缀表达式，并计算只含有数字的后缀表达式的值。本软件支持含小数、多位数等多种操作数的处理，可以计算含加、减、乘、除、百分号、求余、求幂，求阶乘，求三角函数的值等多种运算符和函数的表达式 （2）输入/输出形式 用户可通过打开图标弹出来的计算器界面任意点击操作。对于在输入时发生的简单错误，软件通过弹出对话框给出提示并且在提示错误的同时自动将用户的出错输入略去转化成正确的表达式进行计算，用户也可选择清楚操作然后重新输入a.对于数值和函数表达式软件会输出其表达式的后缀表达式和计算结果并保留六位小数； b.对于字母表达式因字母无法进行数值运算，软件仅输出其后缀表达式的值；清楚按钮可以清楚有已经输入或输出的数据从头计算； 软件窗口可实现最小化。并且输入编辑框可进行修改，复制，粘贴等操作，但后缀表达式和求值结果的编辑框中的内容不可修改，只能执行复制操作。

后缀表达式的计算

#include #include #include #include using namespace std; int priority(char op) //运算符的优先级 { switch(op) { case '(': return 0; break; case '+': case '-': return 1; break; case '*': case '/': return 2; break; default: return -1; break; } } bool IsOperator(char op) //是否为运算符 { if (op == '+' || op == '-' || op == '*' || op == '/') { return true; } return false; } void inTOpost(char s[],vector &v) //转为后缀表达式{ stack stk; int i = 0,len = strlen(s); while(i < len) { if(s[i] >= '0' && s[i] <= '9') {

v.push_back(s[i]); v.push_back(' '); } else if (s[i] == '(') { stk.push(s[i]); } else if (s[i] == ')') { while(stk.top() != '(') { v.push_back(stk.top()); v.push_back(' '); stk.pop(); } stk.pop(); } else if (IsOperator(s[i])) { if (!stk.empty()) { while(!stk.empty() && priority(s[i]) <= priority(stk.top())) { v.push_back(stk.top()); v.push_back(' '); stk.pop(); } } stk.push(s[i]); } i++; } while(!stk.empty()) { v.push_back(stk.top()); v.push_back(' '); stk.pop(); } } bool compute(vector s,int &res) //计算后缀表达式的值 { int i = 0,num; int len = s.size();

后缀表达式求值_数据结构设计

数据结构课程设计 后缀表达式求值 题目：后缀表达式求值 指导老师：高攀 姓名：顾力雄 学院：信息科学与技术学院 专业：计算机科学与技术专业 班级：计科2008级（1）班 学号：2008082258 时间：2009年3月28日

课程设计报告 一、题目：后缀表达式求值； 二、设计目的 1、掌握类模板的应用 2、掌握栈的操作 3、掌握 三、设计内容和要求 运用栈模板在求值过程顺序扫描后缀表达式，每次遇到操作数便将它压入堆栈；遇到运算符，则从栈中弹出两个操作数进行计算，然后再把结果压入堆栈，等到扫描结束时，输出结果，有加减乘除、平方根、sin、cos、tan、arcsin、arcos、arctan、取余、幂运算等等算术。 四、程序结构 后缀表达式 扫描并判断数据类型 运算符则从栈中 取数进行运算数字压入栈中 栈 结果压入栈中输出栈最终结果

五、运行图

参考文献： 刘振鹏编，数据结构（第二版），北京铁道出版社，2007.； 谭浩强编，C++程序设计，北京，清华大学出版社，2004.； 徐晓凯编，数据结构实用教程，第二版，北京，清华大学出版社。

附录：源文件 头文件myStack.h： #ifndef H_StackType #define H_StackType #include #include using namespace std; template //用模板实现的链式结构堆栈类 class stackType { public: const stackType & operator=(const stackType&); void initializeStack(); //构造函数 bool isEmptyStack() const; bool isFullStack() const; void destroyStack(); void push(const Type& newItem); Type top() const; void pop(); stackType(int stackSize=100); stackType(const stackType& otherStack); ~stackType(); private: int maxStackSize; int stackTop; Type *list; void copyStack(const stackType& otherStack); }; //类模板成员函数的实现 template //构造函数 void stackType::initializeStack() { stackTop=0; } template void stackType::destroyStack() //清空栈 { stackTop=0; } template

数学表达式解析(前缀中缀后缀)

它们都是对表达式的记法，因此也被称为前缀记法、中缀记法和后缀记法。它们之间的区别在于运算符相对与操作数的位置不同：前缀表达式的运算符位于与其相关的操作数之前；中缀和后缀同理。 举例： (3 + 4) × 5 - 6 就是中缀表达式 - × + 3 4 5 6 前缀表达式 3 4 + 5 × 6 - 后缀表达式 中缀表达式（中缀记法） 中缀表达式是一种通用的算术或逻辑公式表示方法，操作符以中缀形式处于操作数的中间。中缀表达式是人们常用的算术表示方法。 虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式却是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。对计算机来说，计算前缀或后缀表达式的值非常简单。 前缀表达式（前缀记法、波兰式） 前缀表达式的运算符位于操作数之前。 前缀表达式的计算机求值： 从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素op 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。 例如前缀表达式“- × + 3 4 5 6”： (1) 从右至左扫描，将6、5、4、3压入堆栈； (2) 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素，注意与后缀表达式做比较），计算出3+4的值，得7，再将7入栈； (3) 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈； (4) 最后是-运算符，计算出35-6的值，即29，由此得出最终结果。 可以看出，用计算机计算前缀表达式的值是很容易的。 将中缀表达式转换为前缀表达式： 遵循以下步骤： (1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2； (2) 从右至左扫描中缀表达式； (3) 遇到操作数时，将其压入S2； (4) 遇到运算符时，比较其与S1栈顶运算符的优先级： (4-1) 如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈； (4-2) 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1； (4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较； (5) 遇到括号时：

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

//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.遇到操作数：直接输入到后缀表达式栈 2.遇到运算符，直接入操作符栈 3.遇到左括号：直接将其入栈 4.遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出。 5.遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈 6.最终将操作符栈中的元素依次出栈，输出到后缀表达式栈。 以下是自己写的代码。亲测没有问题。（模拟一个计算器，可以带括号，中间可以空格，只支持整数输入，但是输出结果精确到小数后6位） #include "stdio.h" #define MAX_LEN 100 typedef struct cal{ unsigned char isOper;//是否是操作数1，操作符0.操作数 double Num; //值。或者是操作符的ASCII值 }STRUCT_CAL; #define IS_NUM 0x00 #define IS_OPER 0x01 STRUCT_CAL stackCal[MAX_LEN]; STRUCT_CAL stackCalBack[MAX_LEN]; unsigned char topCal; char stackOper[MAX_LEN]; unsigned char topOper; /***************************************************************** * 堆栈初始化 *****************************************************************/ void stackInit(void)

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

/*************************** //利用栈实现多项式的计算， //如输入: 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）读入一个用中缀表示法表示的简单算术表达式，为方便起见,认为地在字符串后面加入一个特殊字符“；”，并设其优先级为0。 （3）从左至右扫描该算术表达式的每一个字符，如果该字符是数字，则分析到该数字串的结束并将该数字串加入结果字符串，小数点亦算入数字串。 （4）如果该字符是运算符，则按如下操作：优先级高的放在前面，通过出入栈操作。 如果该字符是左括号“（”，则该字符直接压入运算符栈。 如果该字符是右括号“）”，则把运算符栈顶元素弹出直至第一次遇到左括号。如果该字符是算术运算符且其优先关系高于运算符栈顶的运算符，则将该运算符入栈。 否则，将栈顶的运算符从栈中弹出至结果字符串末尾，直至栈顶运算符的优先级低于当前运算符，并将该字符入栈。 （5）重复上述操作（3）-（4）直至扫描完整个简单算术表达式（遇到特殊字符“；”）。 如： 一般简单表达式：((4+5)*6-5)/2+3*2 逆波兰表达式：4 5 + 6 * 5 - 2 / 3 2 * + 步骤如下： 运算符栈结果字符串 第1步：; "" 第2步：;( "" 第3步：;(( "" 第4步：;(( "4" 第5步：;((+ "4 5" 第6步：;( "4 5 +" 第7步：;(* "4 5 +" 第8步：;(* "4 5 + 6" 第9步：;(- "4 5 + 6 *" 第10步：;(- "4 5 + 6 * 5" 第11步：; "4 5 + 6 * 5 -"

第12步：;/ "4 5 + 6 * 5 -" 第13步：;/ "4 5 + 6 * 5 - 2" 第14步：;+ "4 5 + 6 * 5 - 2 /" 第15步：;+ "4 5 + 6 * 5 - 2 / 3" 第16步：;+* "4 5 + 6 * 5 - 2 / 3" 第17步：;+* "4 5 + 6 * 5 - 2 / 3 2" 第18步：;+ "4 5 + 6 * 5 - 2 / 3 2 *" 第19步：; "4 5 + 6 * 5 - 2 / 3 2 * +" 其中运算符优先级如下： * / :2 + - :1 ；:0 逆波兰表达式求值算法： （1）构建一个操作数栈，类型为float； （2）依次扫描逆波兰表达式的每一项； （3）如果是数字串则压入操作数栈； （4）如果是运算符，则从操作数栈顶弹出两个操作数，与运算符进行运算，结果压入操作数栈。 （5）不断重复以上步骤直至扫描完逆波兰表达式。 （6）此时操作数栈必定只剩一个数据，即为逆波兰表达式的值，弹出输出。如：如上表达式计算结果为：30.5.