下载文档原格式
表达式求值问题课程设计一、课程目标知识目标：1. 学生能理解并掌握表达式求值的基本概念和规则，包括运算符优先级、括号的运用等。
2. 学生能够正确构建并简化数学表达式，熟练运用算术运算规则进行求值。
3. 学生能运用所学知识解决实际问题，如根据给定的条件编写表达式，并计算出结果。
技能目标：1. 学生培养逻辑思维能力，通过分析问题，能合理设计表达式并进行求值。
2. 学生通过实际操作，提高解决数学问题的计算速度和准确性。
3. 学生通过小组讨论和问题解决，提升合作能力和交流表达能力。
情感态度价值观目标：1. 学生培养对数学的兴趣，认识到数学在日常生活和未来学习中的重要性。
2. 学生在学习过程中树立正确的价值观，明白诚实求是的科学态度是学习数学的基础。
3. 学生通过解决表达式求值问题，增强自信心，培养勇于尝试和克服困难的积极态度。
课程性质分析：本课程为数学学科，针对五年级学生设计。
该阶段学生具备一定的数学基础和逻辑思维能力，需要通过表达式求值问题进一步巩固算术运算规则，提高解题能力。
学生特点分析：五年级学生处于好奇心强、求知欲旺的时期，他们喜欢探索和解决问题。
但同时，个别学生可能在数学学习上存在困难，需要教师关注并给予个性化指导。
教学要求：1. 教学内容紧密联系课本，确保学生能够掌握基础知识。
2. 教学过程中注重启发式教学，引导学生主动思考、积极参与。
3. 教学评价关注学生的过程表现，鼓励合作与交流，注重培养学生的综合能力。
二、教学内容本课程依据课程目标，结合课本第五章“数的运算”相关内容，组织以下教学大纲：1. 表达式求值基本概念：- 运算符的种类及优先级- 表达式的构成要素- 括号在表达式中的作用2. 算术运算规则：- 加、减、乘、除四则运算- 混合运算的表达式构建与简化- 乘方和开方的运算规则3. 表达式求值方法：- 逐步计算法- 分步骤代入法- 运用算术性质简化表达式4. 实际问题与表达式求值：- 根据实际问题编写表达式- 应用表达式求解问题- 分析实际问题的数量关系教学内容安排与进度：第一课时：表达式求值基本概念及运算符优先级第二课时：算术运算规则及表达式构建第三课时：表达式求值方法及简化技巧第四课时：实际问题与表达式求值的综合应用教材章节关联：《数学》五年级上册第五章“数的运算”：- 第1节 运算顺序与运算定律- 第2节 四则混合运算- 第3节 乘方与开方- 第4节 应用题与表达式求值三、教学方法为有效达成教学目标，本课程将采用以下多样化的教学方法：1. 讲授法：教师通过生动的语言和形象的比喻，对表达式求值的基本概念、运算规则进行讲解，确保学生掌握必要的理论知识。
表达式求值算法总结(C++)表达式求值，一般采用栈和队列的方式来求值，下面介绍表达式求值的两种算法。
方法一、使用两个栈，一个为操作符栈OPTR(operator)，一个是操作数栈OPND(operand)算法过程：当输入3 * ( 4 - 1 * 2 ) + 6 / ( 1 + 1 )时，为简单方便，我们输入时，按照字符的顺序一个一个的处理，比如ch = getchar()。
然后根据ch 的值判断：若ch 是数字，直接压入操作数栈OPND；若ch 是'('，直接入栈OPTR;若ch 是')'，若OPTR 和OPND 非空，弹出OPTR的栈顶操作符，弹出OPND栈顶的两个操作数，做运算，然后见个结果压入栈OPND，直到弹出的OPTR栈顶元素时')';若ch 是操作符(比如+, -, *, /)，如果OPTR栈顶元素是(，直接入栈OPTR，如果不是'('且OPTR栈非空且栈顶元素操作符的优先级大于ch，那么弹出OPTR的栈顶操作符，并弹出OPND中栈顶的两个元素，做运算，将运算结果入栈OPND，此时，重复这一步操作；否则将ch入栈OPTR；若ch为EOF，说明表达式已经输入完成，判断OPTR是否为空，若非空，一次弹出OPTR 栈顶操作符，并与OPND栈顶两个元素做运算，将运算结果入栈OPND，最后表达式的结果即OPND的栈底元素。
以表达式3 * ( 4 - 1 * 2 ) + 6 / ( 1 + 1 )为例，计算过程如下所示：通过上述的计算过程，写出伪代码如下所示：void GetExpress(Stack * OPTR, Stack * OPND){char ch;while ((ch = getchar ()) != EOF) {if (IsDigit (ch)) {PushStack (OPND, ch);}else if (ch == '(')PushStack (OPTR, ch);else if (ch == ')') {while (!IsStackEmpty(OPTR)) {PopStack (OPTR, op);if (op == ')')break;PopStack (OPND, num2);PopStack (OPND, num1);res = Calc (num1, num2, op);PushStack (OPND, res);}}else if (ch == '+' || ch == '-'|| ch == '*' || ch == '/') {while (!IsStackEmpty (OPTR) && GetTop (OPTR)!='(' && GetTop (OPTR)>ch) { PopStack (OPTR, op);PopStack (OPND, num2);PopStack (OPND, num1);res = Calc (num1, num2, op);PushStack (OPND, res);}if (IsStackEmpty (OPTR) || GetTop(OPTR)=='(')PushStack (OPTR, ch);}}}// 当表达式输入完成后，需要对OPTR栈和OPND中的元素进行运算int GetValue(Stack * OPTR, Stack * OPND){while (!IsStackEmpty (OPTR)) {PopStack (OPTR, op);PopStack (OPND, num2);PopStack (OPND, num1);res = Calc (num1, num2, op);PushStack (OPND, res);}// 最后的操作数栈OPND栈顶元素即是表达式的值return GetTop(OPND);}PS: 上面没有指出表达式非法的情况方法二：采用中缀表达式的方法，求取表达式的中缀表达式，借用一个操作符栈OPTR和中缀表达式队列Queue，求取中缀表达式，然后对中缀表达式求值。
字符串表达式求值（⽀持多种类型运算符）⼀、说明1. 输⼊字符串为中缀表达式，⽆需转为后缀表达式2. ⽀持的运算符包括：算术运算符："+,-,*,/"关系运算符：">,<,>=,<=,=,!="(注意等于运算符采⽤的是⼀个等号)逻辑运算符："&&,||"3. ⽀持⼤于10的数字，不⽀持负数操作数，但⽀持中间结果和返回值为负数⼆、算法原理&步骤本⽂算法对中缀表达式形式字符串进⾏求值，同时⽀持与或运算和逻辑运算(若含有关系运算符或者逻辑运算符，则输出为1或者0)。
类似于加减乘除，将关系运算符和逻辑运算符看作优先级低的运算符进⾏处理，优先级：算术运算符>关系运算符>逻辑运算符。
步骤：1. 初始化两个空堆栈，⼀个存放操作数，⼀个存放运算符。
2. 从左⾄右扫描输⼊字符串，依次读取。
2.1 若为操作数，则压⼊操作数栈；2.2 若为运算符，判断其优先级是否⼤于运算符栈栈顶元素优先级。
若⼤于栈顶元素优先级，则直接压栈；否则，弹出栈顶元素operator，同时依次从操作数栈中弹出两个元素number1,number2，计算表达式(number2 operator number1)的值value，并将值value压⼊操作数栈。
重复上述过程直⾄当前扫描的操作符优先级⼤于栈顶元素，然后将当前运算符压栈。
3. 弹出运算符栈顶元素operator，同时依次从操作数栈中弹出两个元素number1,number2，计算表达式(number2 operator number1)的值value，并将值value压⼊操作数栈。
重复上述过程直⾄运算符栈为空。
4. 此时操作数栈应该只有⼀个元素，即为表达式的值。
三、代码&测试求值函数：1/* 字符串表达式求值2 * @param input: 输⼊的字符串3 * @param output: 表达式的值，若含有关系运算符则为1或者04 * return 计算过程是否正常5*/6bool ExpValue(string input,int& output)7 {8 stack<int> operand_stack;9 stack<string> operator_stack;1011char prev = 0; // 上⼀个属于运算符的字符12for (int i = 0; i < input.size(); i++)13 {14char c = input[i];15// prev是否是⼀个完整运算符16if (!isOperator(c) && prev)17 {18string new_op = string("").append(1, prev);19 addNewOperator(new_op, operand_stack, operator_stack);20 prev = 0;21 }2223// 数字24if (isdigit(c))25 {26int val_c = c - '0';27if (i > 0 && isdigit(input[i - 1]))28 {29int top_num = operand_stack.top();30 top_num = top_num * 10 + val_c;31 operand_stack.pop();32 operand_stack.push(top_num);33 }34else35 operand_stack.push(val_c);36 }37// 运算符字符38else if (isOperator(c))39 {40// 处理两字符运算符41if (prev)42 {43string new_op = string("").append(1, prev).append(1, c);44 addNewOperator(new_op, operand_stack, operator_stack);45 prev = 0;46 }47else48 prev = c;49 }50else if (c == '(')51 operator_stack.push("(");52else if (c == ')')53 {54// 处理括号内的运算符55while (operator_stack.top()!="(")56 {57int num1 = operand_stack.top();58 operand_stack.pop();59int num2 = operand_stack.top();60 operand_stack.pop();61string op = operator_stack.top();62 operator_stack.pop();6364int val = Calculate(num2, num1, op);65 operand_stack.push(val);66 }67 operator_stack.pop(); // 弹出"("68 }69 }70 assert(operand_stack.size() == operator_stack.size() + 1);71// 弹出所有运算符72while(!operator_stack.empty())73 {74int num2 = operand_stack.top();75 operand_stack.pop();76int num1 = operand_stack.top();77 operand_stack.pop();78string op = operator_stack.top();79 operator_stack.pop();8081int val = Calculate(num1, num2, op);82 operand_stack.push(val);83 }8485if (operand_stack.size() == 1) {86 output = operand_stack.top();87return true;88 }89return false;90 }其中⽤到的⼦函数有：/* 判断字符是否属于运算符 */bool isOperator(char c){switch (c){case'-':case'+':case'*':case'/':case'%':case'<':case'>':case'=':case'!':case'&':case'|':return true;default:return false;}}/* 获取运算符优先级 */int getPriority(string op){int temp = 0;if (op == "*" || op == "/" || op == "%")temp = 4;else if (op == "+" || op == "-")temp = 3;else if (op == ">" || op == "<" || op == ">=" || op == "<="|| op == "=" || op == "!=")temp = 2;else if (op == "&&" || op == "||")temp = 1;return temp;}/** 返回⼀个两元中缀表达式的值* syntax: num_front op num_back* @param num_front: 前操作数* @param num_back: 后操作数* @param op: 运算符*/int Calculate(int num_front, int num_back, string op){if (op == "+")return num_front + num_back;else if (op == "-")return num_front - num_back;else if (op == "*")return num_front * num_back;else if (op == "/")return num_front / num_back;else if (op == "%")return num_front % num_back;else if (op == "!=")return num_front != num_back;else if (op == ">=")return num_front >= num_back;else if (op == "<=")return num_front <= num_back;else if (op == "=")return num_front == num_back;else if (op == ">")return num_front > num_back;else if (op == "<")return num_front < num_back;else if (op == "&&")return num_front && num_back;else if (op == "||")return num_front || num_back;return0;}/* 新运算符⼊栈操作 */void addNewOperator(string new_op, stack<int>& operand_stack, stack<string>& operator_stack) {while (!operator_stack.empty() && getPriority(operator_stack.top()) >= getPriority(new_op)){int num2 = operand_stack.top();operand_stack.pop();int num1 = operand_stack.top();operand_stack.pop();string op = operator_stack.top();operator_stack.pop();int val = Calculate(num1, num2, op); operand_stack.push(val);}operator_stack.push(new_op);}View Code测试结果：int main(){string s0 = "10-1*10+3%2";string s1 = "100 + (3-33)*2";string s2 = "20+1 >= 20 && 20+1 < 20"; string s3 = "10>20 || 10/1>=5";int ret = -1;if (ExpValue(s0, ret))cout << s0 << "的值: " << ret << endl; if (ExpValue(s1, ret))cout << s1 << "的值: " << ret << endl; if (ExpValue(s2, ret))cout << s2 << "的值: " << ret << endl; if (ExpValue(s3, ret))cout << s3 << "的值: " << ret << endl; return0;}上述代码的执⾏结果为：。
ＸＸXＸXX大学《数据结构》课程设计报告班级：学号：姓名：指导老师:目录一算术表达式求值一、需求分析二、程序得主要功能三、程序运行平台四、数据结构五、算法及时间复杂度六、测试用例七、程序源代码二感想体会与总结算术表达式求值一、需求分析一个算术表达式就是由操作数(oｐeranｄ）、运算符(operator）与界限符（deｌimiter)组成得。
假设操作数就是正整数，运算符只含加减乘除等四种运算符,界限符有左右括号与表达式起始、结束符“#”，如：＃(7+15）*（2３—２8/４）#。
引入表达式起始、结束符就是为了方便.编程利用“算符优先法”求算术表达式得值.二、程序得主要功能（1）从键盘读入一个合法得算术表达式，输出正确得结果。
(2）显示输入序列与栈得变化过程。
三、程序运行平台Ｖｉsｕaｌ C＋+6、0版本四、数据结构本程序得数据结构为栈。
（1）运算符栈部分：struct SqStaｃk ／/定义栈{char *base； //栈底指针ｃｈａr *toｐ; ／/栈顶指针inｔstacｋsiｚe； //栈得长度};inｔInitSｔack (SqＳｔack &ｓ) //建立一个空栈S{ｉf （!(s、ｂａse= (char ＊）ｍalloc(5０＊ｓizeof（chａr）)）)exｉt（0）；ｓ、ｔop=s、bａse;s、staｃksiｚｅ=５0；retuｒn OK；}ｃhar GeｔTop（SqStack s,char &e) /／运算符取栈顶元素｛iｆ (s、ｔop==s、ｂase) //栈为空得时候返回EＲROR｛ﻩ prｉntf(＂运算符栈为空！＼n")；ﻩ reｔurn ERＲＯR;｝elsee＝*（s、ｔoｐ-1); //栈不为空得时候用ｅ做返回值，返回S得栈顶元素，并返回OK returnＯＫ;｝ｉnt Push(SqStacｋ＆s，cｈａr ｅ） //运算符入栈｛if （s、tｏp—s、baｓe >= ｓ、ｓtacksｉzｅ）ﻩ{ｐriｎtf（＂运算符栈满!＼n"）;ﻩs、basｅ=（cｈaｒ*）reａlloｃ(s、bａｓe，(s、sｔackｓｉze+5)*ｓizeoｆ(cｈar））；//栈满得时候,追加5个存储空间ｉf(！s、basｅ)exｉt （OVERＦＬOW）；s、top=s、ｂａsｅ+s、ｓｔacｋsize;s、ｓtaｃksiｚｅ+=５;}ﻩ＊(s、ｔop）＋＋=e；／/把e入栈ﻩｒeturn OK;}ｉnｔ Pop(SqStaｃk &ｓ，char ＆ｅ） /／运算符出栈｛ｉｆ (s、toｐ==s、base) ／/栈为空栈得时候，返回ERＲOＲ｛ｐrintf（＂运算符栈为空!\n”）;ﻩ return ERROＲ;}else｛ﻩﻩe=＊-—ｓ、tｏp；/／栈不为空得时候用e做返回值，删除S得栈顶元素，并返回ＯK return OK；}}iｎt StackTｒaｖerse（ＳqStacｋ&ｓ)／/运算符栈得遍历｛ﻩchar ＊t；ﻩt=s、ｂａｓｅ；ﻩif (s、top＝=s、baｓe）｛ﻩ printｆ（”运算符栈为空！\ｎ”)； //栈为空栈得时候返回ＥＲRORｒeturn ERＲOＲ;}ｗhile（t！＝s、tｏp)｛ﻩﻩｐrｉｎｔf（" %c",＊t)； //栈不为空得时候依次取出栈内元素t++;ﻩ}ｒeturｎ EＲRＯR；｝（2）数字栈部分：strｕｃt SqSｔackn//定义数栈｛ｉnt *bａse; //栈底指针ｉnt＊tｏp； //栈顶指针ｉnｔ sｔacksｉze； //栈得长度｝;inｔIｎｉtStackｎ (SqSｔackn &s) //建立一个空栈Ｓ{s、base=（int＊）malｌoc（50*sｉzeof(int）);if(！ｓ、ｂase）eｘiｔ（OVEＲFLＯW）；//存储分配失败s、top=s、base；s、stacksizｅ=5０;reｔuｒn OK；｝ｉｎt GｅtToｐn(ＳqＳtａcｋn s,inｔ＆e) //数栈取栈顶元素{if（s、ｔop=＝s、base）{prinｔｆ(＂运算数栈为空!\ｎ＂);//栈为空得时候返回ERRORﻩ rｅturｎ ERROR;}eｌseﻩe＝＊（s、toｐ-1);／/栈不为空得时候，用e作返回值，返回S得栈顶元素，并返回OＫreturｎＯK；｝int Pｕshn（SｑStａckn ＆s，int ｅ) //数栈入栈｛if（s、tｏp—s、ｂasｅ＞＝s、stacksiｚe)｛ﻩﻩprｉｎｔf（"运算数栈满!\ｎ"）；／/栈满得时候,追加5个存储空间ﻩs、base=(int＊）realloc (s、baｓe,(s、stａcksize＋5)＊sｉzｅof（ｉnt));ｉf（!s、base) ｅxit (ＯＶERFLOW)；ﻩs、top=ｓ、bａsｅ＋ｓ、stacｋsize;//插入元素e为新得栈顶元素s、stacksｉｚe+=5；}*（s、top）++=e; /／栈顶指针变化returｎOK;}ｉｎt Popｎ(ＳｑSｔacｋn ＆s，iｎt &e)//数栈出栈｛ﻩif （s、top=＝ｓ、base）｛ﻩ pｒiｎtｆ（"运算符栈为空！\n＂);//栈为空栈得视时候，返回ERRＯＲﻩ retｕrn ERROR；ﻩ｝ｅlse｛ﻩﻩe=＊—-ｓ、tｏp；／/栈不空得时候，则删除S得栈顶元素,用e返回其值，并返回OK ﻩreturｎOK；｝}ｉnt StacｋＴraveｒsｅn（SqStackn &s)/／数栈遍历{ﻩiｎｔ＊t;ﻩｔ=s、basｅ ;ﻩif（s、top==s、basｅ）ﻩ｛pｒinｔf(＂运算数栈为空！\n”）；//栈为空栈得时候返回ERRORﻩ rｅｔｕrn ERＲＯＲ；ﻩ｝ﻩwｈile（t！=ｓ、ｔop)ﻩ{priｎtf(” ％d”，*ｔ); /／栈不为空得时候依次输出t＋＋;｝return ERRＯR；｝五、算法及时间复杂度１、算法:建立两个不同类型得空栈,先把一个‘＃’压入运算符栈。
表达式求值(数据结构)表达式求值(数据结构)1.引言在计算机科学中，表达式求值是一项重要的任务。
它涉及解析和计算数学或逻辑表达式，以得出最终结果。
表达式可以包括数字、变量、运算符和函数，通过采用特定的计算规则，我们可以将这些表达式转化为具体的数值或逻辑结果。
2.表达式的基本概念2.1 数字在表达式中，数字是最基本的元素。
可以是整数或浮点数，用于进行算术计算。
2.2 变量变量是用于存储和代表值的符号，它可以在表达式中使用。
变量可以通过赋值操作来获得具体的值，在表达式求值过程中，变量会被相应的数值替换。
2.3 运算符运算符是用于执行特定操作的符号。
常见的算术运算符包括加法(+), 减法(-), 乘法和除法(/）逻辑运算符包括与(&&), 或(--------) 和非(!）在表达式求值中，运算符的优先级和结合性规则是非常重要的。
2.4 函数函数是一段封装了特定功能的代码块，可以接受输入参数并返回一个结果。
在表达式中，函数可以用于处理特定的数据操作或算法。
例如，sin(x) 和cos(x) 是常见的三角函数。
3.表达式求值的步骤3.1 词法分析首先，需要对表达式进行词法分析，将表达式分解为一个个的词法单元，例如数字、变量、运算符和函数等。
词法分析可以使用正则表达式或者逐字符扫描的方式进行。
3.2 语法分析在得到词法单元序列后，需要进行语法分析，根据语法规则验证表达式的结构是否正确。
语法分析可以使用自顶向下的LL(1)分析方法或者自底向上的LR分析方法。
3.3 语义分析一旦表达式的结构验证通过，就需要进行语义分析。
语义分析的任务是根据语法树运用特定的求值规则，将表达式转换为具体的数值或逻辑结果。
在语义分析过程中，需要处理变量的赋值和函数的调用。
4.表达式求值的例子为了更好地理解表达式求值的过程，以下是一个例子：________表达式：________ 2 (3 + 4) ●5 / 24.1 词法分析：________将表达式分解为以下词法单元：________ 数字(2, 3, 4, 5), 运算符(, +, -), 括号(), 除法运算符(/)4.2 语法分析：________根据语法规则验证表达式的结构是否正确，构建语法树：________-/ \\// \\ / \\2 + 5 2/ \\3 44.3 语义分析：________根据语法树使用求值规则，依次计算每个节点的值：________●节点：________ 2 (7) ●5 / 2●节点：________ 2 7 ●5 / 2●节点：________ 14 ●5 / 2●节点：________ 14 ●2.5●最终结果：________ 11.55.附件本文档没有涉及附件。
表达式求值算法表达式求值算法是计算机科学中的重要概念之一，用于计算数学表达式的结果。
在编程语言中，表达式求值是一项基本的操作，并且经常在计算过程中需要用到。
本文将介绍一些常见的表达式求值算法及其实现。
1. 逆波兰表达式法逆波兰表达式法是一种用于计算数学表达式的算法，它使用后缀表达式（也称为逆波兰表达式）来表示表达式。
逆波兰表达式是将操作符放在操作数之后的一种表示方法。
对于任意一个数学表达式，都可以通过将中缀表达式转换为后缀表达式，然后使用栈结构计算得到结果。
逆波兰表达式法的优点是计算顺序明确，不需要考虑运算符的优先级和括号的处理。
2. 中缀表达式转后缀表达式法中缀表达式是我们常见的数学表达式，如 3 + 4 * 5。
在中缀表达式中，操作符的优先级和括号起着很大的作用。
为了将中缀表达式转换为后缀表达式，我们需要使用到栈结构。
具体的算法如下：- 遍历中缀表达式的每个元素。
- 如果是操作数，则直接输出。
- 如果是操作符，则判断其与栈顶操作符的优先级，决定是否将其压入栈。
- 如果是左括号，则直接压入栈。
- 如果是右括号，则依次弹出栈顶操作符，并输出，直到遇到左括号为止。
- 遍历完表达式后，如果栈不为空，则依次弹出栈顶操作符，并输出。
3. 后缀表达式求值法后缀表达式（逆波兰表达式）的求值方法相对简单。
我们可以使用栈结构来计算后缀表达式的结果。
具体的算法如下：- 遍历后缀表达式的每个元素。
- 如果是操作数，则将其压入栈。
- 如果是操作符，则弹出栈顶的两个操作数，执行相应的计算，并将结果压入栈。
- 遍历完后缀表达式后，栈中最后剩下的元素即为计算结果。
4. 二叉树表示法除了逆波兰表达式法和中缀表达式法，我们还可以使用二叉树来表示表达式，并通过遍历二叉树来计算表达式的结果。
具体的算法如下：- 构建二叉树，将表达式的操作符作为根节点，将操作数作为叶节点。
- 通过后序遍历二叉树，计算出每个子树的值，并将结果返回给其父节点。
栈的应⽤——表达式求值 表达式求值是程序设计语⾔编译中的⼀个基本问题，它的实现就是对“栈”的典型应⽤。
本⽂针对表达式求值使⽤的是最简单直观的算法“算符优先法”。
本⽂给出两种⽅式来实现表达式求值，⽅式⼀直接利⽤中缀表达式求值，需要⽤到两个栈，操作数栈和操作符栈。
⾸先置操作数栈为空栈，操作符栈仅有“#”⼀个元素。
依次读⼊表达式中的每个字符，若是操作数则进操作数栈，若是操作符则和操作符栈的栈顶运算符⽐较优先权作相应操作，直⾄整个表达式求值完毕。
⽅式⼆⾸先把中缀表达式转换为后缀表达式并存储起来，然后利⽤读出的后缀表达式完成求值，其本质上是⽅式⼀的分解过程。
表达式求值的代码如下：#include <iostream>#include "stack"#include "map"using namespace std;/* 只能求⼀位整数的加减乘除混合运算 */map<char, pair<int, int>> priority; // 存放各个操作符的栈内栈外优先级,first是栈内,second是栈外char infix[50]; // 存放初始的中缀表达式char postfix[50]; // 存放转化的后缀表达式int result;void MakePriority() // 构造运算符优先级表{priority.insert(make_pair('#', make_pair(0, 0))); // isp(#)=0, icp(#)=0priority.insert(make_pair('\n', make_pair(0, 0))); // isp(\n)=0, icp(\n)=0 表达式结尾的'#'⽤'\n'代替,这样可以省略表达式末尾的结束符'#'priority.insert(make_pair('(', make_pair(1, 6))); // isp(()=1, icp(()=6priority.insert(make_pair('*', make_pair(5, 4))); // isp(*)=5, icp(*)=4priority.insert(make_pair('/', make_pair(5, 4))); // isp(/)=5, icp(/)=4priority.insert(make_pair('%', make_pair(5, 4))); // isp(%)=5, icp(%)=4priority.insert(make_pair('+', make_pair(3, 2))); // isp(+)=3, icp(+)=2priority.insert(make_pair('-', make_pair(3, 2))); // isp(-)=3, icp(-)=2priority.insert(make_pair(')', make_pair(6, 1))); // isp())=6, icp())=1}void InfixToPostfix() // 把中缀表达式转换为后缀表达式{int i = 0;stack<char> optrStack; // 操作符栈char optr; // optr为栈顶的操作符optrStack.push('#');while (!optrStack.empty()){if (isdigit(infix[i])) // 是操作数则直接输出(追加到postfix结尾){postfix[strlen(postfix)] = infix[i];postfix[strlen(postfix) + 1] = '\0';i++; // 读⼊中缀表达式的下⼀个字符}else// 是操作符, ⽐较优先级{optr = optrStack.top(); // 取出栈顶操作符if (priority[infix[i]].second > priority[optr].first) // icp(infix[i]) > isp(optr),infix[i]⼊栈{optrStack.push(infix[i]);i++;}else if (priority[infix[i]].second < priority[optr].first)// icp(infix[i]) < isp(optr),optr退栈并输出{postfix[strlen(postfix)] = optr;postfix[strlen(postfix) + 1] = '\0';optrStack.pop();}else// icp(infix[i]) = isp(optr),退栈但不输出,若退出的是'(',则继续读⼊下⼀个字符{optrStack.pop();if (optr == '(')i++;}}}}void CalculateByPostfix() // 通过后缀表达式求值{int i = 0;stack<int> opndStack; // 操作数栈int left, right; // 左右操作数int value; // 中间结果int newOpnd;while (postfix[i] != '#' && i < strlen(postfix)){switch (postfix[i]){case'+':right = opndStack.top(); // 从操作数栈中取出两个操作数opndStack.pop();left = opndStack.top();opndStack.pop();value = left + right;opndStack.push(value); // 中间结果⼊栈break;case'-':right = opndStack.top();opndStack.pop();left = opndStack.top();opndStack.pop();value = left - right;opndStack.push(value);break;case'*':right = opndStack.top();opndStack.pop();left = opndStack.top();opndStack.pop();value = left * right;opndStack.push(value);break;case'/':right = opndStack.top();opndStack.pop();left = opndStack.top();opndStack.pop();if (right == 0){cerr << "Divide by 0!" << endl;}else{value = left / right;opndStack.push(value);}break;default:newOpnd = (int)(postfix[i] - 48); // 操作数直接⼊栈opndStack.push(newOpnd);break;}i++;}result = opndStack.top();}void CalculateByInfix() // 直接利⽤中缀表达式求值{int i = 0;stack<char> optrStack; // 操作符栈stack<int> opndStack; // 操作数栈char optr; // optr为操作符栈顶的操作符int left, right, value; // 左右操作数以及中间结果optrStack.push('#');optr = optrStack.top();while (!optrStack.empty()) // 直到操作符栈为空{if (isdigit(infix[i])) // 是操作数, 进操作数栈{value = (int)(infix[i] - 48);opndStack.push(value);i++;}else// 是操作符, ⽐较优先级{optr = optrStack.top(); // 取出操作符栈顶的操作符if (priority[infix[i]].second > priority[optr].first) // icp(infix[i]) > isp(optr),infix[i]⼊栈 {optrStack.push(infix[i]);i++;}else if (priority[infix[i]].second < priority[optr].first) // icp(infix[i]) < isp(optr),optr退栈并输出{optrStack.pop();right = opndStack.top(); // 从操作数栈中取出两个操作数opndStack.pop();left = opndStack.top();opndStack.pop();switch (optr){case'+':value = left + right;opndStack.push(value); // 中间结果⼊栈break;case'-':value = left - right;opndStack.push(value); // 中间结果⼊栈break;case'*':value = left * right;opndStack.push(value); // 中间结果⼊栈break;case'/':if (right == 0){cerr << "Divide by 0!" << endl;}else{value = left / right;opndStack.push(value);}break;default:break;}}else{optrStack.pop();if (optr == '(')i++;}}}result = opndStack.top();}int main(){MakePriority(); // 构造运算符优先级表cout << "请输⼊中缀表达式：";cin >> infix;cout << "直接利⽤中缀表达式求值为：";CalculateByInfix();cout << result << endl;cout << "转化为后缀表达式：";InfixToPostfix();for (int i = 0;i < strlen(postfix);i++){cout << postfix[i];}cout << endl;cout << "利⽤后缀表达式求值为：";CalculateByPostfix();cout << result << endl;return0;} 为了⽅便起见，本⽂只是简单的设计了⼀个针对⼀位整数的四则运算进⾏求值的算法，对于处理多位整数的四则运算，需要对本⽂接受输⼊的数据类型进⾏“升阶”，把字符数组换成字符串数组，将⼀个整数的多位数字存⼊⼀个字符串进⾏处理。
数据结构课程设计报告项目名称：表达式求值学号：班级：姓名：指导老师：计算机科学与技术2014年12月20日1.问题描述：表达式求值问题主要是通过使用栈和队列来解决问题。
我们在书写表达式时总是以中缀形式输入，也就是将运算符放在操作数中间，但是计算机处理数据时，运算符却跟在两个操作数之后，这种表现形式称为后缀表达式，所以在书写程序时要注意两种表现形式之间的转换。
2.设计思路：①一个表达式由运算符和操作数两部分构成，它的操作数由0-9这十个数字构成，它的运算符有+、-、*、/四种。
一般在表达式中，括号也会改变表达式运算的优先级，所以将括号也看做运算符，并将其的优先级规定为最低。
②通过栈将中缀表达式转换成后缀表达式的算法思想：顺序扫描中缀表达式，当读到数字时直接将其送至队列中，当读到运算符时，将栈中所有优先级高于或等于该运算符的运算符出栈，送至输出队列中，再将当前运算符入栈，当读到左括号时，入栈，当读到右括号时，将靠近栈顶的第一个左括号上面的运算符全部依次出栈，送至输出队列中，再删除栈中的左括号。
为了方便边界条件（栈空）的判断，提高算法的运行效率，在扫描读入中缀表达式之前、在空栈中预先压入一个“#”字符作为栈底元素，另外，在表达式的最后增加一个“#”字符作为中缀表达式的结束标志，该结束符与栈底元素“#”配对。
本算法不包括输入表达式的语法检查，但可以过滤掉输入符号之间的空格。
执行上述程序若输入中缀表达式字符串：9-（2*4=7）/5+3#,就会得到后缀表达式：9247*+5/3+.其中，运算符栈和存放后缀表达式的队列的变化过程如表2—1所示。
表2—1 中缀表达式到后缀表达式的转换过程示例转换步骤中缀表达式的读入运算符栈OS 后缀表达式PostQ 初始9-(2+4*7)/5+3# # 空1 -（2+4*7/5+3# # 92 (2+4*7)/5+3# - 93 2+4*7)/5+3# -( 94 +4*7)/5+3# -( 9 25 4*7)/5+3# -(+ 9 26 *7)/5+3# -(+ 9 2 47 7)/5+3# -(+* 9 2 48 )/5+3# -(+* 9 2 4 79 /5+3# - 9 2 4 7 * +10 5+3# -/ 9 2 4 7 * +11 +3# -/ 9 2 4 7 * + 512 3# + 9 2 4 7 * + 5 / -13 # + 9 2 4 7 * + 5 /- 314 空9 2 4 7 * + 5 / - 3 +③.后缀表达式的计算在后缀表达式中，不仅不需要括号，而且还完全免除了运算符优先级规则。
对于后缀表达式来说，仅仅使用一个自然规则，即从左到右顺序完成计算，这个规则对于计算机而言是很容易实现的。
下面将讨论如何用就算计算机了实现计算后缀表达式的算法。
如果在表达式中只有一个运算符，如像53*这样的表达式，显然计算过程非常重要，可立即执行。
但在多数情况下，后缀表达式中都是多于一个运算符，因此，必须要像保存输入数字一样保存其中间结果。
在算法中要有一个数字字符到数值的转换。
下面以后缀表达式9247*+5/-3+为例，使用上述算法计算该表达式，计算过程如表2-2所示表2-2 后缀表达式的计算过程示例计算步骤后缀表达式的读入运算结果栈VS 初始9 2 4 7 * + 5 / - 3 + 空1 2 4 7 * + 5 / - 3 + 92 4 7 * + 5 / -3 + 2 93 7 * + 5 /- 3 +4 2 94 * +5 /- 3 + 7 4 2 95 + 5 / - 3 + 28 2 96 5 / - 3 + 30 2 97 / - 3 + 5 30 98 - 3 + 6 990 3 + 310 + 3 311 空 63.数据结构定义://操作数栈定义typedef struct{float data[MaxSize];int top;}OpStack,SeqStack;4.系统功能模块介绍:（）流程图如下图所示：5.运行与调试分析：输入表达式：9/(8-5)+66.体会：这次课程设计让我更加了解大一学到的C和数据结构程序设计与算法。
设计题目要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧。
这次课程设计让我有一个深刻的体会，那就是细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。
就像我在写PushStack ()函数时，忘了指针的地址符值不用加*号，这一点小小的错误也耽误了我几十分钟，所以说细节很重要。
设计程序时，也要不怕遇到错误，否则会让自己心情烦躁，很难找出错误，要冷静思考。
同时也要善于请教别人，因为人总是很难发现自己的错误。
在这次程序设计中，我在了解和掌握数据结构程序设计的过程中，发现了自己许多的不足之处，在以后的上机中应更加注意，同时体会到C语言具有的语句简洁，使用灵活，执行效率高等特点，也发现上机的重要作用，特别对算术表达式有了深刻的理解。
主程序:#include<stdio.h>#include<string.h>typedef char DataType;#define MaxSize 50//操作数栈定义typedef struct{float data[MaxSize];int top;}OpStack,SeqStack;//函数声明void InitStack(SeqStack *s);//初始化int StackEmpty(SeqStack s);//判断栈是否为空int GetTop(SeqStack s,DataType *e);//取栈顶元素int PushStack(SeqStack *s,DataType e);//入栈int PopStack(SeqStack *s,DataType *e);//出栈void TranslateE(char s1[],char s2[]);//将中缀表达式转化为后缀表达式float ComputeE(char s[]);//计算后缀表达式void main(){char a[MaxSize],b[MaxSize];float f;printf("请输入表达式:\n");gets(a);printf("中缀表达式为:%s\n",a);TranslateE(a,b);printf("转换为后缀表达式为:%s\n",b);f=ComputeE(b);printf("该表达式的计算结果为:%f\n",f);}float ComputeE(char a[])//计算后缀表达式的值{OpStack s; //定义一个操作数栈int i=0;float x1,x2,value,result;s.top=-1; //初始化栈while(a[i]!='\0') //依次扫描后缀表达式中的每个字符{if(a[i]!=' '&&a[i]>='0'&&a[i]<='9')//如果当前字符是数字字符,转换为数字{value=0;while(a[i]!=' ')//如果不是空格,说明数字字符是两位数以上的{value=10*value+a[i]-'0';i++;}s.top++;s.data[s.top]=value; //处理之后将数字进栈}else //如果当前字符是运算符{switch(a[i]) //将栈中的数字出栈两次,然后用当前的运算符进行运算,再将结果入栈{case '+':{x1=s.data[s.top];s.top--;x2=s.data[s.top];s.top--;result=x1+x2;s.top++;s.data[s.top]=result;break;}case '-':{x1=s.data[s.top];s.top--;x2=s.data[s.top];s.top--;result=x2-x1;s.top++;s.data[s.top]=result;break;}case '*':{x1=s.data[s.top];s.top--;x2=s.data[s.top];s.top--;result=x1*x2;s.top++;s.data[s.top]=result;break;}case '/':{x1=s.data[s.top];s.top--;x2=s.data[s.top];s.top--;result=x2/x1;s.top++;s.data[s.top]=result;break;}}i++;}}if(s.top!=-1)//如果栈不空,将结果出栈,并返回{result=s.data[s.top];s.top--;if(s.top==-1)return result;else{printf("表达式错误");return(-1);}}else return -1;}void TranslateE(char str[],char exp[]){SeqStack s;char ch;DataType e;int i=0,j=0;InitStack(&s);ch=str[i];i++;while(ch!='\0') //依此扫描中缀表达式中的每个字符{switch(ch){case '(': //遇到左括号,将其进栈PushStack(&s,ch);break;case ')': //遇到右括号,将栈中的操作数出栈,并将其存入数组exp中while(GetTop(s,&e)&&e!='('){PopStack(&s,&e);exp[j]=e;j++;}PopStack(&s,&e);//将左括号出栈break;case '+':case '-': //遇到加减号,将栈顶字符出栈,并将其存入数组exp中,然后将当前运算符进栈while(!StackEmpty(s)&&GetTop(s,&e)&&e!='('){PopStack(&s,&e);exp[j]=e;j++;}PushStack(&s,ch);break;case '*': //遇到乘除号,先将同级运算符出栈,并存入数组exp中,然后将当前的运算符进栈case '/':while(!StackEmpty(s)&&GetTop(s,&e)&&e=='/'||e=='*'){PopStack(&s,&e);exp[j]=e;j++;}PushStack(&s,ch);break;case ' ':break;default: //遇到操作数,则将操作数直接送入数组exp中,并在其后添加一个空格,用来分隔数字字符while(ch>='0'&&ch<='9'){exp[j]=ch;j++;ch=str[i];i++;}i--;exp[j]=' ';j++;}ch=str[i];//读入下一个字符i++;}while(!StackEmpty(s))//将栈中所有剩余的运算符出栈,送入数组exp中{PopStack(&s,&e);exp[j]=e;j++;}exp[j]='\0';}void InitStack(SeqStack *s)//初始化{s->top=0;//把栈顶指针置为0}int StackEmpty(SeqStack s)//判断栈是否为空{if(s.top==0)//判断栈顶指针是否为0return 1;elsereturn 0;int GetTop(SeqStack s,DataType *e)//取栈顶元素{if(s.top<=0)//在取栈顶元素之前,判断栈是否为空{printf("栈已为空!\n");return 0;}else{*e=(char)s.data[s.top-1];//取栈顶元素return 1;}}int PushStack(SeqStack *s,DataType e)//入栈{if(s->top>=MaxSize)//判断栈是否满了{printf("栈已满,不能进栈!\n");return 0;}else{s->data[s->top]=e;//e元素进栈s->top++;//修改栈顶指针return 1;}}int PopStack(SeqStack *s,DataType *e)//出栈{if(s->top==0){printf("栈已空,不能出栈!\n");return 0;}else{s->top--;*e=(char)s->data[s->top];return 1;}}。
