学院计算机科学与技术系课程设计报告20 12 ～20 13 学年第 2 学期课程数据结构与算法 课 程 设 计 名 称算数表达式的求解学生周丽娟学号1104012024专业班级11 计本 3 班指导老师红20 13 年 3 月[问题描述]（算数表达式的求解）给定一个算数表达式，通过程序求出最后的结果。[要求]1、从键盘输入要求解的算术表达式；2、采纳栈结构进行算数表达式的求解过程；3、能够推断算数表达式的正确与否；4、对于错误表达式给出提示；5、对于正确表达时给出最后的结果。1、问题分析和任务定义有题目可知，程序要求给定一算数表达式并计算最后的结果，我们知道，在高级语言中，任何一个表达式都是有操作数、运算符和界限符组成。在计算过程中，还要考虑表达式中有无括号以与左右括号之分。由于运算符有优先级的高低，因此一个算数表达是不可能总是按顺序执行。 通过以上可知，可以用栈来实现运算符的优先级完成算术表达式的求解。为实现算法的优先级，设置两个栈：一个称为操作数栈 opnd，用以寄存操作数和运算结果，另一个为操作符栈 optr，用以寄存运算符。该算法的基本思想是：（1）首先置操作数栈 opnd 为空栈，表达式结束符“#”为操作符栈 optr 的栈底元素。（2）依次读入表达式中每个字符，若为操作数，则进 opnd 栈；若是运算符，则与 optr栈的栈顶运算符比较优先级后做相应操作：若当前操作符大于 optr 栈的栈顶，则当前操作符入栈；否则，opnd 栈的栈顶元素、次栈顶元素出栈，同时 optr 栈的栈顶元素也出栈，形成运算，并将结果压入 opnd 栈，直至整个表达式求值完毕（即 optr 栈的栈顶元素和当前读入的字符均为“#”）。对于算术表达式的输入，本程序采纳 gets()的方法读入，将运算符‘+’，‘-’，‘*’，‘/’，‘（’，‘）’，‘#’存储在数组中时，定义表达式求解函数，在函数中推断读入的字符，假如是运算符，将这些字符入操作符 optr 栈，并比较优先级，推断是否运算。若读入的字符为‘0’到‘9’之间的数字时，用字符相减转化为整型，然后将转化后的整型再转化为ASCII 的形式压入操作数栈 opnd 中。2、数据结构的选择和概要设计（1）存储结构设计本程序主要采纳顺序栈结构类型（Stack）来存储表达式计算中的数据。程序中需要建立两个栈，一个栈用于寄存运算符，另一个则用于寄存操作数和计算结果，故需要建立两个顺序栈结构类型。（2）算数优先级设计对一任意的表达式，由于表达式中运算符的优...
