数据结构作业.doc

目 录
一、设计思想……………………………………………………….01
二、算法流程图…………………………………………………….01
三、源代码………………………………………………………….03
四、运行结果……………………………………………………….16
五、遇到的问题及解决…………………………………………….16
六、心得体会……………………………………………………….17
设计思想
第一种算法：
先把中缀表达式变为后缀表达式，然后对后缀表达式进行计算。
变后缀表达式：首先用结构体建立一个符号栈，用于存放运算符和运算符优先级，用字符串储存一个运算表达式，用一个字符数组储存后缀表达式。建立一个引索从字符串开始依次扫描，当遇到数字和小数点直接储存在数组中，每取完一个数字或小数点后用“|”隔开，若扫描的为操作符，如果此时符号栈为空，符号直接入栈，否则需要与栈顶的运算符进行优先级比较。若优先级比栈中操作符的优先级高则入栈，否则栈顶符号出栈，直到栈顶运算符优先级小于扫描运算符的优先级（若为“（”，则无条件入字符栈；若为“）”，不如栈，栈内操作符出栈，直到遇到“（”为止），每出栈一个操作符用“|”隔开。
后缀表达式计算：首先建立一个操作数栈，用于存放运算数。查看存放后缀表达式的数组若是存放的操作数，直接进栈；若遇见操作符从操作数栈中输出两个数，将栈顶的数位于操作符的后面另一个数放在操作符前面，然后进行计算将结果送入栈中，依次进行直到数栈为空，最后操作数栈中的数即为运算结果。
第二种算法：
对中缀表达式直接进行计算。
首先需要建立两个栈，一个操作符栈，用于存放操作符；一个操作数栈，用于存放运算数。定义一个字符串数组来储存需要计算的中缀表达式并定义一个引索，用引索从字符串的开始一次扫描。如果扫描到的是运算数或小数点，则进行循环的扫描知道取出整个数字，将其放入操作数栈；如果扫描到的是操作符，如果栈为空，符号可以直接进入符号栈，若栈不为空，进行优先级的比较。如果扫描到的运算符优先级高于栈顶操作符的优先级则符号可以直接入栈；如果扫描到的运算符优先级比符号栈顶元素优先级低，就从符号栈中取出一个运算符，从操作数栈中取出两个数，先取出的操作数位于操作符后，再取出的数位于操作符前，然后进行计算，之后依次比较直到扫描到的操作符可以入栈为止，把计算出的操作数存放在操作数栈（若为“（”，则无条件入字符栈；若为“）”，不如栈，栈内操作符出栈，直到遇到“（”为止），按照此规则进行计算，直到操作符栈为空为止。最终存放在操作符栈的数即为中缀表达式的结果，并将结果进行输出。
二、算法流程图
图1为第一种算法的流程图，先将中缀表达式转为后缀表达式；图2为第二种算法的流程图，建立两个栈，直接对表达式进行计算。
中缀运算表达式

取出字符的判断

若为数字或小数点 若为操作符
操作符优先级比较
若为括号
括号类型
储存在字符数组中
优先级高
若为右括号
从字符栈取 出 操 做 符
入栈
入栈
若为左括号 优先级低
出栈储存在数组中

是否为左括号
存放在数组中
不是左括号
出栈
是左括号
得到后缀表达式
若为数字或小数点