本文已收录于专栏
?《
educoder数据结构与算法_大耳朵宋宋的博客-CSDN博客
》?
?任务描述?
本关任务要求通过实现函数
double ComputePostfix(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; // 数据元素类型
此外，为了计算后缀表达式，我们定义了如下函数，这个函数需要你来实现：
-
double ComputePostfix(char* s);
-
/*
-
s是后缀表达式符号串，如果表达式是7 8 +,那么s[0]=’7’,s[1]=’8’,s[2]=’+’。
-
该函数返回表达式计算结果。
-
*/
为了简化你的实现，假设表达式中的操作数都是一个
非负的个位数
。后面的测试中，输入数据将符合这一要求。
?编程要求?
本关的编程任务是补全 step2/Postfix.cpp 文件中
ComputePostfix
函数，以实现计算后缀表达式的功能。具体要求如下：
-
本关任务要求通过实现函数
double ComputePostfix(char* s)
来计算后缀表达式； - 具体请参见后续测试样例。
本关涉及的代码文件 Postfix.cpp 的代码框架如下：
-
#include <stdio.h>
-
#include <stdlib.h>
-
#include "LnkStack.h"
-
#include "postfix.h"
-
double ComputePostfix(char* s)
-
{
-
// 请在此添加代码，补全函数ComputePostfix，计算后缀表达式
-
/********** Begin *********/
-
/********** End **********/
-
}
?测试说明?
本关的测试过程如下：
- 平台编译 step2/Main.cpp ，然后链接相关程序库并生成 exe 可执行文件；
- 平台运行该可执行文件，并以标准输入方式提供测试输入；
- 平台获取该可执行文件的输出，然后将其与预期输出对比，如果一致则测试通过；否则测试失败。
输入输出说明：
输入格式
： 输入一个后缀表达式。表达式中的操作数都是一个
非负的个位数
。
输出格式
： 输出该表达式的值。
以下是平台对 step2/Main.cpp 的测试样例：
样例输入：
12+96-*
样例输出：
result = 9.000000
开始你的任务吧，祝你成功！
?AC_Code?
#include <stdio.h>
#include <stdlib.h>
#include "LnkStack.h"
#include "Postfix.h"
double ComputePostfix(char* s)
{
// 请在此添加代码，补全函数ComputePostfix，计算后缀表达式
/********** Begin *********/
LinkStack* sd=LS_Create();
int i=0;
T k,top1,top2;
while(s[i])
{
switch(s[i])
{
case'+':
LS_Pop(sd,top1);
LS_Pop(sd,top2);
k=top1+top2;
LS_Push(sd,k);
break;
case'-':
LS_Pop(sd,top1);
LS_Pop(sd,top2);
k=top2-top1;
LS_Push(sd,k);
break;
case'*':
LS_Pop(sd,top1);
LS_Pop(sd,top2);
k=top1*top2;
LS_Push(sd,k);
break;
case'/':
LS_Pop(sd,top1);
LS_Pop(sd,top2);
k=top2/top1;
LS_Push(sd,k);
break;
default:
LS_Push(sd,(int)(s[i]-48));
}
i++;
}
T res;
LS_Top(sd,res);
LS_Free(sd);
return res;
/********** End **********/
}