设计成绩 报告成绩 指导老师 一．实验目的
掌握线性表的使用，熟练掌握栈的各种操作函数，能借助于栈的功能将中缀表达式转换为后缀表达式，并利用后缀表达式求值。 二．实验要求及实验环境 实验要求：1.使用栈来进行操作
2.能提示用户输入正确的中缀表达式的值，并输出正确的后缀表达式 3.利用后缀表达式求值并输出 实验环境：CodeBlocks(visual stdio)/win 7系统
三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系） 主要的数据类型：
Word结构体类型的定义，含有两个变量字符型和double型 栈类型的定义，其中数组类型为word型，栈的各种操作函数的定义 主函数int main()中
char mid[100] 存放用户输入的中缀表达式
int m 记录用户输入的中缀表达式所含的字符数
word m_word[100] 可将中缀中的字符和数字分开存放在两个不同类型的数组中，并实现将连续的多位整数至于统一存储空间 word post[100] 存放转换后的后缀表达式的值 int l 记录后缀表达式所含字符长度 int r 存放根据后缀表达式所求的值
在分开存储中缀表达式的运算符和数字的void analysis(char post[100],word m_word[100])函数中
char post[100] 存放中缀表达式
word m_word[[100] 结构体类型的数组可以区分多位数，小数，运算符 double sum 由字符转换后的多位数或小数
依次扫描中缀表达式的字符，若连续的为一串数字，则将他们转换为多位数，
存放于word 类型的m_word数组中并且型为num下，所下标对应的型为type置‘0’，若为操作符，则直接存于m_word数组中并且型为type下。 在表达式转换void Exchange(word a[100],word b[100],int m,int &l)函数中 word a[100] 存放的是中缀表达式 word b[100] 存放转换后的后缀表达式 int m 标记数组a中元素个数 int l 标记数组b中元素个数
STACK O 临时存放运算符（ + - * / ）并对其进行相应的入栈出栈弹栈操作
在求值double Add(word post[100],int l)函数中 word post[100] 后缀表达式结构体数组 int l 记录数组长度
STACK S 将后缀表达式的数字按某种方式压入此栈，经过运算后弹出
最后一个元素即为所求的值
1. 逻辑设计：（1）输入中缀表达式
2. 借助analisis,将输入的单一字符变为相应的整数和小数，存放在一结构体数组中，此数组可区分数和操作符
3.将中缀表达式转换为后缀表达式需要借助于一个栈来存放操作符，具体方法如下：
①从左到右一次扫描中缀表达式的每一个字符，如果为多位数或浮点数，则直接将它们写入后缀表达式中。
②如果遇到的是开括号“（”，则将它们压入一个操作符栈（不需要与栈顶操作符相比较），它表明一个新的计算层次的开始，在遇到和它匹配的闭括号“）”时，将栈中的元素弹出来并放入后缀表达式中，直到栈顶元素为“(”时，将栈顶元素“（”弹出（不需要加入后缀表达式），表明这一层括号内的操作处理完毕。 ③如果遇到的是操作符，则将该操作符和操作符栈顶元素比较：
●1、当所遇到的操作符的优先级小于或等于栈顶元素的优先级时，则取出栈顶元素放入后缀表式，
并弹出该栈顶元素，反复执行直到栈顶元素的优先级小于当前操作符的优先级； ●2、当所遇到的操作符的优先级大于栈顶元素的优先级的时则将它压入栈中。 ④重复上述步骤，直到将中缀表达式扫描完毕，最后弹出栈中的所有元素并放入后缀表达式中，转换结束。
(3)求后缀表达式式的值，将后缀表达式中的数字直接压入新栈中，若为运算符，则将栈顶元素和次栈顶元素做相应的运算，则新栈中存储的最后一个值为我们所求的表达式的结果。
流程图见下页：
主程序的流程图为：
开始 int main 函数 输出表达式的运算结果 提示用户输入中缀表达式 analysis函数 将中缀表达式存入结构体数组中 Exchange函数 将中缀表达式转换为后缀表达式 输出后缀表达式 Add函数 后缀表达式求值 结束
中缀表达式的等价转换analysis函数流程图：