中缀表达式转换为后缀表达式c++b编程.doc

设计成绩报告成绩指导老师一实验目的 掌握线性表的使用，熟练掌握栈的各种操作函数，能借助于栈的功能将中缀表达式转换为后缀表达式，并利用后缀表达式求值。二实验要求及实验环境实验要求：1.使用栈来进行操作 2.能提示用户输入正确的中缀表达式的值，并输出正确的后缀表达式 3.利用后缀表达式求值并输出实验环境：CodeBlocks(visual stdio)/win 7系统三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系）主要的数据类型：Word结构体类型的定义，含有两个变量字符型和double型栈类型的定义，其中数组类型为word型，栈的各种操作函数的定义主函数int main()中char mid100 存放用户输入的中缀表达式int m 记录用户输入的中缀表达式所含的字符数word m_word100 可将中缀中的字符和数字分开存放在两个不同类型的数组中，并实现将连续的多位整数至于统一存储空间 word post100 存放转换后的后缀表达式的值int l 记录后缀表达式所含字符长度int r 存放根据后缀表达式所求的值在分开存储中缀表达式的运算符和数字的void analysis(char post100,word m_word100)函数中 char post100 存放中缀表达式word m_word100 结构体类型的数组可以区分多位数，小数，运算符double sum 由字符转换后的多位数或小数依次扫描中缀表达式的字符，若连续的为一串数字，则将他们转换为多位数，存放于word 类型的m_word数组中并且型为num下，所下标对应的型为type置0，若为操作符，则直接存于m_word数组中并且型为type下。在表达式转换void Exchange(word a100,word b100,int m,int &l)函数中word a100 存放的是中缀表达式word b100 存放转换后的后缀表达式int m 标记数组a中元素个数int l 标记数组b中元素个数STACK O 临时存放运算符（ + - * / ）并对其进行相应的入栈出栈弹栈操作在求值double Add(word post100,int l)函数中word post100 后缀表达式结构体数组int l 记录数组长度STACK S 将后缀表达式的数字按某种方式压入此栈，经过运算后弹出最后一个元素即为所求的值1. 逻辑设计：（1）输入中缀表达式2. 借助analisis,将输入的单一字符变为相应的整数和小数，存放在一结构体数组中，此数组可区分数和操作符3.将中缀表达式转换为后缀表达式需要借助于一个栈来存放操作符，具体方法如下：从左到右一次扫描中缀表达式的每一个字符，如果为多位数或浮点数，则直接将它们写入后缀表达式中。如果遇到的是开括号“（”，则将它们压入一个操作符栈（不需要与栈顶操作符相比较），它表明一个新的计算层次的开始，在遇到和它匹配的闭括号“）”时，将栈中的元素弹出来并放入后缀表达式中，直到栈顶元素为“(”时，将栈顶元素“（”弹出（不需要加入后缀表达式），表明这一层括号内的操作处理完毕。如果遇到的是操作符，则将该操作符和操作符栈顶元素比较：1、当所遇到的操作符的优先级小于或等于栈顶元素的优先级时，则取出栈顶元素放入后缀表式， 并弹出该栈顶元素，反复执行直到栈顶元素的优先级小于当前操作符的优先级；2、当所遇到的操作符的优先级大于栈顶元素的优先级的时则将它压入栈中。重复上述步骤，直到将中缀表达式扫描完毕，最后弹出栈中的所有元素并放入后缀表达式中，转换结束。(3)求后缀表达式式的值，将后缀表达式中的数字直接压入新栈中，若为运算符，则将栈顶元素和次栈顶元素做相应的运算，则新栈中存储的最后一个值为我们所求的表达式的结果。流程图见下页：开始主程序的流程图为：输出表达式的运算结果int main 函数Exchange函数analysis函数将中缀表达式存入结构体数组中提示用户输入中缀表达式将中缀表达式转换为后缀表达式输出后缀表达式后缀表达式求值Add函数结束中缀表达式的等价转换analysis函数流程图：依次扫描输入的中缀表达式扫描字符为0至9间的任意字符时为操作符时循环扫描下一位直到它不为数字转换为多位数或小数存入结构体数组型为Num中,将type型置空下一位为.存入结构体数组型为type中中缀表达式转换为后缀表达式的Exchange函数流程图：判断表达式数组中字符属性建立操作符栈若为）弹出栈中元素若为数字存入后缀表达式数组中若为（压入操作符栈与栈顶元素优先级比较小于等于大于取栈顶元素放入数组，直到优先级大于，并压栈压栈栈非空弹出存入数组输出 根据后缀表达式求值Add函数流程图：判断数组中元素属性若为数字若为操作符直接入栈弹出栈顶和次栈顶元素，并转换为整型根据运算符进行相应操作，将结果入栈弹出栈顶元素，即为所求的值四测试结果 五系统不足与经验体会1当输入除数为零时，系统会自动报错，但在程序中并未有报错语句，应该在后期加以改进2熟练掌握栈的各种操作，是写好本次试验的前提条件3后期学习中应该加强动手能力，多上机操作试验，因为你永远想不到自己所写的程序会发生什么样的错误六，附录（源代码，带注释）#include using namespace std;#define maxlength 100struct word /定义word结构体类型，其中包含两个变量char type;double num;struct STACK /定义栈的结构体类型int top;word elementsmaxlength;void MakeNull(STACK &S)/初始化栈S.top=maxlength;bool Empty(STACK S)/判栈空if(S.topmaxlength-1)return 1;elsereturn 0;word Top(STACK S)/弹出栈顶元素word empty=0,0;if(Empty(S)return empty;elsereturn(S.elementsS.top);word Pop(STACK &S)/删除栈顶元素if(Empty(S)std:cerr栈空不能出栈;return S.elementsS.top+;void Push(word x,STACK &S)/将元素压入栈中if (S.top=0)std:cerr栈满不能入栈;S.top=S.top-1;S.elementsS.top=x;word Display(STACK S) word empty=0,0; cout栈中元素有; while(!Empty(S) empty=Pop(S); coutempty.type; coutendl;word iDisplay(STACK S) word empty=0,0; cout栈中元素有; while(!Empty(S) empty=Pop(S); coutempty.num; coutendl;void Exchange(word a100,word b100,int m,int &l) /将中缀表达式转换为后缀表达式STACK O; /定义空栈OMakeNull(O);int i;for(i=0;im;i+) if(ai.type=0)/如果为数字时bl=ai;/直接存入后缀表达式数组l+;if(ai.type=()Push(ai,O); Display(O);if (ai.type=+|ai.type=-)while(!Empty(O)&Top(O).type!=()bl+=Pop(O); Display(O);Push(ai,O); Display(O);if(ai.type=/|ai.type=*)while(!Empty(O)&Top(O).type!=-&Top(O).type!=+&Top(O).type!=()bl+=Pop(O); Display(O);Push(ai,O); Display(O);if(ai.type=)while(Top(O).type!=()bl+=Pop(O); Display(O);Pop(O); Display(O);while(!Empty(O)/当栈非空时，弹出栈顶元素存入后缀表达式数组bl+=Pop(O); Display(O);int j;for(j=0;jl;j+)/输出后缀表达式数组if (bj.type=0)coutbj.num ;elsecoutbj.type;coutendl;double Add(word post100,int l)/求和STACK S;MakeNull(S);for(int i=0;i=0&posti=0&posti=0&posti=9)/按小数存储sum+=(double)(posti-0)/k;i+;k*=10.0;m_wordj.type=0;m_wordj.num=sum;j+;elsem_wordj.type=posti;i+;j+;int main()double r;char mid100;word m_word100;int i=0,m=0;cout请输入中缀表达式mid