数据结构课程实践报告模板-表达式计算

1、问题描述与分析

算数表达式一般都写成中缀形式，即运算符总是出现在两个操作数之间（单目运算符除外），称为中缀表达式。编译系统对中缀表达式的处理方法是先把它转换为后缀表达式。在后缀表达式中，运算符位于两个操作数的后面，并且没有括号，其运算符次序就是其执行计算的次序。后缀表达式计算过程的规则非常简单：从左到右依次扫描，当读到运算符时，就对该运算符前面的两个操作数执行相应的运算，直至得到表达式的结果。

本程序主要模拟编译系统计算中缀表达式的过程，先将中缀表达式转换成相应的后缀表达式，再根据后缀表达式计算出表达式的值。这个问题的解决主要是栈的一个应用。

因为本程序仅是模拟，没有判断输入的中缀表达式是否合法，容错性不强，另外也仅能对一位数的中缀表达式进行转换和计算，功能上还有许多局限性，本程序处理的中缀表达式中仅允许出现六种运算符，且都是双目运算符。

2、数据结构设计和基本算法设计方法的选择

2.1 中缀表达式转换成后缀表达式

为完成中缀表达式转换成相应的后缀表达式，设计了infix2postfix类。为了方便用户使用，它只有4个接口函数，包括两个构造函数，一个设置中缀表达式的函数setInfixExp和一个返回后缀表达式的函数postfixExp。所有表达式均采用string来存储，运算符用堆栈来临时存储，并用map的数据结构来定义优先级。下面给出了infix2posfix类的声明和部分定义。

class infix2postfix { public:

infix2postfix(){};

infix2postfix(const string& infixExp):infix(infixExp){}; void setInfixExp(const string& infixExp){infix=infixExp;}; string postfixExp(); private:

- 1 -

string infix; //用于转换的中缀表达式 string postfix; //后缀表达式 stack stk;//用于存储运算符的堆栈

map oper_prio;//用于存储运算符的优先级 void set_priority();

//设置运算符('+','-','*','/','%','^')的优先级 };

中缀表达式转换成后缀表达式功能的实现是栈的一个典型应用，主要应用栈的“后进先出”的特性及预先设计好的运算符优先级。在转换过程中设置了下运算符栈。本程序的栈直接使用了C++标准模板库STL提供的stack容器。

2.2 根据后缀表达式计算出表达式的值

设计了postfixEval类来实现后缀表达的计算，它只有3个接口函数以方便用户调用。这3个公有函数分别为默认的构造函数、设置后缀表达式的函数setPostfixExp，计算后缀表达式的函数evaluate。下面给出了postfixEval类的声明和部分定义。

/*postfixEval类的声明*/ class postfixEval { public:

postfixEval(){}; //设置后缀表达式

void setPostfixExp(const string& postfixExp){postfix=postfixExp;}; //计算后缀表达式并返回其值 int evaluate(); private:

string postfix;//待求值的后缀表达式 stackstk;

void getOperands(int&left,int&right);//从堆栈中取得左右操作数 int compute(int left,int right,char op) const; bool isOperator(char ch) const;//判断是否为运算符 };

后缀表达式的计算也是栈的典型应用，在计算过程中需要设置一个操作数栈。

3、软件结构设计

- 2 -

由于本程序主要是实现模拟表达式的计算，因此主要有两个功能模块：中缀表达式转换成后缀表达式和根据后缀表达式计算出表达式的值。

4、算法设计与实现

4.1 中缀表达式转换成后缀表达式的算法设计

中缀表达式转换成后缀表达式的步骤为：

1）设置一个运算符栈，初始时效地栈顶运算符置为\"#\"。

2）按顺序扫描中缀表达式，当输入为操作数时就将其输出到后缀表达式中。 3）当输入为运算符时，则比较输入运算符和栈顶运算符的优先级。若输入运算符的优先级高于栈顶运算符的优先级，则将输入运算符入栈；否则，栈顶运算符的优先级高于或等于输入运算符的优先级，弹出栈顶运算符至后缀表达式，然后重新比较输入运算符和更新后的栈顶运算符的优先级。

4）当输入运算符为\"(\"时，直接将\"(\"入栈。

5）当输入运算符为\")\"时，将栈顶运算符出栈至后缀表达式，直至栈顶为\"（\"时，将\"(\"出栈并抛弃，同时\")\"也抛弃。

6）中缀表达式扫描完毕后，将运算符栈依次出栈至后缀表达式直至栈顶为\"#\"时停止。

具体定义如下：

string infix2postfix::postfixExp() {

postfix = \"\"; set_priority(); stk.push(\"#\"); int i = 0;

string input,topstk; for(;itopstk = stk.top();//取运算符栈的栈顶

input = infix.substr(i,1);//取出当前待输入的符号

if (!oper_prio[input])//如果输入的符号不是运算符，直接放入postfix postfix+=input;

else {

//待输入的符号是个运算符，进一步判断它的优先级和运算符栈顶运算符的优先级

if (oper_prio[input]>oper_prio[topstk])//比运算符栈顶运算符的优先级高 {

if(input.compare(\")\")==0)

//若待输入的运算符为\")\出栈直至\"(\"，否则直接入栈

- 3 -

{

while(topstk.compare(\"(\")!=0) {

postfix+=topstk; stk.pop();

topstk=stk.top(); }

stk.pop(); }

else

stk.push(input);

}

else//比运算符栈顶运算符的优先级低

{

if(input.compare(\"(\")!=0)

{ //若待输入的运算符不为\"(\出栈直到遇到栈顶运算符的优

//先级高的情况，否则直接入栈 postfix+=topstk; stk.pop(); continue; }

stk.push(input); } } ++i; }

topstk=stk.top();

while (topstk.compare(\"#\")!=0) {

postfix+=topstk; stk.pop(); topstk=stk.top(); }

return postfix; }

4.2 计算后缀表达式的算法设计

后缀表达式计算的算法：设置一个用于存放操作数的栈，从左到右依次扫描后缀表达式，每读入一个操作数就将其入栈，每读入一个运算符就从操作数栈中取出两个栈顶元素施以该运算操作，并将运算结果作为新的操作数入栈。重复此过程直至将后缀表达式读完。最后，栈顶操作数即为该后缀表达式的运算结果。具体定义如下：

int postfixEval::evaluate()

- 4 -

{

int i,left,right,expValue; char ch;

//扫描后缀表达式直至表达式结束 for(i=0;ich=postfix[i];//取得当前字符

if (isdigit(ch)) //如果为操作数，压入操作数栈

stk.push(ch-'0');

else if(isOperator(ch))

{ //若为运算符则取出其前两个操作数执行运算，并将结果压入操作数栈 getOperands(left,right);

stk.push(compute(left,right,ch));

} }

expValue = stk.top();stk.pop();//操作数的栈顶即为最后的运算结果 return expValue; }

5、调试分析

下面是中缀表达式计算的测试函数主体部分，它测试了中缀表达式转换成后缀表达式类infix2postfix，和后缀表达式的计算类postfixEval的使用情况。

int main(int argc, char *argv[]) {

string infix,postfix; infix2postfix iexp; postfixEval pexp;

cout<<\"******本程序模拟一位数的中缀表达式转化为后缀表达式及其运算*******\"<>infix;

while(infix.compare(\"q\")!=0) {

cout<<\"你输入的中缀表达式为：\"<- 5 -

cout<<\"其相应的后缀表达式为\"<cout<<\"表达式的运算值=\"<>infix; } return 0; }

运行结果如图5-1所示。

图5-1 程序运行截图

6、总结

1）综合实践过程的收获；

2）遇到问题以及解决问题的思路和方法； 3）程序调试能力的思考 ；

4）在综合实践设计过程中对《数据结构与算法分析》课程的认识等内容。

- 6 -

附录：程序代码清单

#include #include #include

using namespace std;

/*infix2postfix类的声明*/ class infix2postfix {

public:

infix2postfix(){};

infix2postfix(const string& infixExp):infix(infixExp){}; void setInfixExp(const string& infixExp){infix=infixExp;}; string postfixExp();

private:

string infix; //用于转换的中缀表达式 string postfix; //后缀表达式

stack stk;//用于存储运算符的堆栈

map oper_prio;//用于存储运算符的优先级 void set_priority();

//设置运算符('+','-','*','/','%','^')的优先级 };

/*postfixEval类的声明*/ class postfixEval {

public:

postfixEval(){}; //设置后缀表达式

void setPostfixExp(const string& postfixExp){postfix=postfixExp;}; //计算后缀表达式并返回其值 int evaluate();

private:

string postfix;//待求值的后缀表达式

stackstk;

void getOperands(int&left,int&right);//从堆栈中取得左右操作数 int compute(int left,int right,char op) const;

bool isOperator(char ch) const;//判断是否为运算符 };

void infix2postfix::set_priority()

- 7 -

{

oper_prio[\"#\"] = 1; oper_prio[\"(\"] = 2; oper_prio[\"+\"] = 3; oper_prio[\"-\"] = 3; oper_prio[\"*\"] = 4; oper_prio[\"/\"] = 4; oper_prio[\"%\"] = 4; oper_prio[\"^\"] = 5; oper_prio[\")\"] = 6; }

//求取并返回后缀表达式

string infix2postfix::postfixExp() {

postfix = \"\"; set_priority(); stk.push(\"#\"); int i = 0;

string input,topstk; for(;i{

topstk = stk.top();//取运算符栈的栈顶

input = infix.substr(i,1);//取出当前待输入的符号

if (!oper_prio[input])//如果输入的符号不是运算符，直接放入postfix

postfix+=input;

else {//待输入的符号是个运算符，进一步判断它的优先级和运算符栈顶运算符的优先级 if (oper_prio[input]>oper_prio[topstk])//比运算符栈顶运算符的优先级高 {

if(input.compare(\")\")==0)

//若待输入的运算符为\")\出栈直至\"(\"，否则直接入栈 {

while(topstk.compare(\"(\")!=0) {

postfix+=topstk; stk.pop(); topstk=stk.top(); }

stk.pop(); } else

stk.push(input);

- 8 -

}

else//比运算符栈顶运算符的优先级低

{

if(input.compare(\"(\")!=0)

{ //若待输入的运算符不为\"(\出栈直到遇到栈顶运算符的

//优先级高的情况，否则直接入栈 postfix+=topstk; stk.pop(); continue; }

stk.push(input); } }

++i; }

topstk=stk.top();

while (topstk.compare(\"#\")!=0) {

postfix+=topstk; stk.pop();

topstk=stk.top(); }

return postfix; }

int postfixEval::evaluate() {

int i,left,right,expValue; char ch;

//扫描后缀表达式直至表达式结束

for(i=0;ich=postfix[i];//取得当前字符

if (isdigit(ch)) //如果为操作数，压入操作数栈

stk.push(ch-'0'); else if(isOperator(ch))

{ //若为运算符则取出其前两个操作数执行运算，并将结果压入操作数栈 getOperands(left,right); stk.push(compute(left,right,ch));

} } expValue = stk.top();stk.pop();//操作数的栈顶即为最后的运算结果 return expValue; }

- 9 -

void postfixEval::getOperands(int& left,int& right) {

right = stk.top(); stk.pop();

left = stk.top(); stk.pop(); }

int postfixEval::compute(int left,int right,char op) const {

int value; switch(op)

{

case '+':value = left+right; break;

case '-':value = left-right; break;

case '*':value = left*right;

break;

case '/':if (right == 0)

cout<<\"postfixEval出现 除0 错误\"<case '%':if (right == 0)

cout<<\"postfixEval出现 除0 错误\"<case '^':if (left==0 && right == 0)

cout<<\"postfixEval出现未定义的0^0现象\"<0) {

value *=left; right--; } break; }

return value; }

bool postfixEval::isOperator(char ch) const {

- 10 -

return ch=='+'||ch=='-' || ch=='*'||ch=='/'||ch=='%'||ch=='^'; }

int main(int argc, char *argv[]) {

string infix,postfix; infix2postfix iexp;

postfixEval pexp;

cout<<\"****本程序模拟一位数的中缀表达式转化为后缀表达式及其运算*******\"<>infix;

while(infix.compare(\"q\")!=0)

{

cout<<\"你输入的中缀表达式为：\"<cout<<\"其相应的后缀表达式为\"<pexp.setPostfixExp(postfix);

cout<<\"表达式的运算值=\"<>infix; }

system(\"PAUSE\"); return 0; }

- 11 -