任务描述
本关任务要求通过实现函数double ComputeInfix(char* s)来计算中缀表达式。
相关知识
中缀表达式的计算需要用到栈。关于链接存储的栈，其中已实现了如下操作：
创建栈：创建一个链式栈。具体操作函数定义如下： LinkStack* LS_Create()；
释放栈：释放栈所占用的空间。具体操作函数定义如下： void LS_Free(LinkStack* ls)；
清空一个栈：将链式栈变为空栈。具体操作函数定义如下： void LS_MakeEmpty(LinkStack* ls)；
判断栈是否为空：若栈为空，则返回true，否则返回false。具体操作函数定义如下： bool LS_IsEmpty(LinkStack* ls)；
求栈的长度：获取链式栈的长度。具体操作函数定义如下： int LS_Length(LinkStack* ls)；
将元素 x 进栈：将 x 进栈，若满栈则无法进栈，返回false，否则返回true。具体操作函数定义如下： void LS_Push(LinkStack* ls, T x)；
出栈：出栈的元素放入item。若出栈成功(栈不为空)，则返回true；否则(空栈)，返回false。具体操作函数定义如下： bool LS_Pop(LinkStack* ls, T& item)；
获取栈顶元素：获取栈顶元素放入item中。若获取失败(空栈)，则返回false，否则返回true。具体操作函数定义如下： bool LS_Top(LinkStack* ls, T& item)；
打印栈中元素：从栈顶到栈底打印各结点数据元素。具体操作函数定义如下： void LS_Print(LinkStack* ls)。
在计算中缀表达式的过程中，你可以根据需要调用以上操作。因为表达式的计算结果可能是浮点数，所以这里将栈的数据元素类型设置为了double类型。
typedef double T; // 数据元素类型
此外，为了计算中缀表达式，我们定义了如下函数，其中的 1）已经实现，你需要实现 2）： 1）：
void compute(LinkStack* so, LinkStack* sd);/*so为运算符栈sd为操作数栈*/
该函数处理步骤：
- 从运算符栈出栈一个运算符；
- 从操作数栈出栈两个操作数；
- 用出栈的运算符对出栈的操作数进行运算；
- 将运算结果进操作数栈。
2）：
double ComputeInfix(char* s);/*s是中缀表达式符号串，如果表达式是7+8,那么s[0]=’7’,s[1]=’+’,s[2]=’8’。该函数返回表达式计算结果。*/
在实现 2）的过程中，可以调用 1）。为了简化你的实现，假设表达式中的操作数都是一个非负的个位数。后面的测试中，输入数据将符合这一要求。
编程要求
本关的编程任务是补全 step1/Infix.cpp 文件中ComputeInfix函数，以实现计算中缀表达式的功能。具体要求如下：
- 本关任务要求通过实现函数
double ComputeInfix(char* s)来计算中缀表达式； - 具体请参见后续测试样例。
本关涉及的代码文件 Infix.cpp 的代码框架如下：
#include <stdio.h> #include <stdlib.h> #include "LnkStack.h" #include "infix.h" // void compute(LinkStack* so, LinkStack* sd) //++++++++++++++++++++++++++++++++++++++++++++++ // so 运算符栈 // sd 操作数栈 // 1 从运算符栈出栈一个运算符 // 2 从操作数栈出栈两个操作数 // 3 用出栈的运算符对出栈的操作数进行运算 // 4 将运算结果进操作数栈 //+++++++++++++++++++++++++++++++++++++++++++++++ { T a,b,c,d; LS_Pop(so,c); LS_Pop(sd,a); LS_Pop(sd,b); if (c=='*') d=b*a; else if (c=='/') d=b/a; else if (c=='+') d=b+a; else if (c=='-') d=b-a; else printf("never occur!"); LS_Push(sd, d); } double ComputeInfix(char* s) { // 请在此添加代码，补全函数ComputeInfix，计算中缀表达式 /********** Begin *********/ /********** End **********/ }
测试说明
本关的测试过程如下：
- 平台编译 step1/Main.cpp ，然后链接相关程序库并生成 exe 可执行文件；
- 平台运行该可执行文件，并以标准输入方式提供测试输入；
- 平台获取该可执行文件的输出，然后将其与预期输出对比，如果一致则测试通过；否则测试失败。
输入输出说明： 输入格式： 输入一个中缀表达式。表达式中的操作数都是一个非负的个位数。 输出格式： 输出该表达式的值。
以下是平台对 step1/Main.cpp 的测试样例：
样例输入： (1+2)*(9-6) 样例输出： result = 9.000000
开始你的任务吧，祝你成功！
AC_Code
#include <stdio.h> #include <stdlib.h> #include "LnkStack.h" #include "Infix.h" // void compute(LinkStack* so, LinkStack* sd) //++++++++++++++++++++++++++++++++++++++++++++++ //so 运算符栈 //sd 操作数栈 //1 从运算符栈出栈一个运算符 //2 从操作数栈出栈两个操作数 //3 用出栈的运算符对出栈的操作数进行运算 //4 将运算结果进操作数栈 //+++++++++++++++++++++++++++++++++++++++++++++++ { T a,b,c,d; LS_Pop(so,c); LS_Pop(sd,a); LS_Pop(sd,b); if (c=='*') d=b*a; else if (c=='/') d=b/a; else if (c=='+') d=b+a; else if (c=='-') d=b-a; else printf("never occur!"); LS_Push(sd, d); } double ComputeInfix(char* s) //计算中缀表达式 { int i=0; LinkStack* so=LS_Create(); //运算符栈 LinkStack* sd=LS_Create(); //操作数栈 while(s[i]) { if ('0'<=s[i] && s[i]<='9') { LS_Push(sd, s[i++]-48); continue; } if(s[i]=='('||LS_IsEmpty(so)) { LS_Push(so, s[i++]); continue; } if(s[i]==')') { T topitem; while(LS_Top(so,topitem) && topitem !='(' ) { compute(so, sd); } LS_Pop(so,topitem); i++; continue; } if(s[i]=='*'||s[i]=='/') { T c; LS_Top(so,c); if (c=='*' || c=='/') { compute(so, sd); } LS_Push(so, s[i++]); continue; } if(s[i]=='+'||s[i]=='-') { T topitem; while(LS_Top(so,topitem) && topitem !='(' ) { compute(so, sd); } LS_Push(so, s[i++]); continue; } } while(!LS_IsEmpty(so)) { compute(so, sd); } T res; LS_Top(sd,res); LS_Free(so); LS_Free(sd); return res; }
