四则运算表达式求值（栈+二叉树，c++版）

数据结构——实验报告

HUNAN UNIVERSITY

课程实习报告

题 目： 四则运算表达式求值

学生姓名： 周华毅

学生学号： 201308010411

1 / 11

专业班级： 计科1304 指导老师： 吴帆 完 成 日 期 ： 2015/5/1

数据结构——实验报告

一、需求分析

a) 四则运算表达式求值，将四则运算表达式用中缀表达式表示，然后转换为后缀表达

式，并计算结果。

b) 本程序要求利用二叉树后序遍历来实现表达式的转换，同时可以使用实验2的结果

来求解后缀表达式的值。

c) 在字符界面上输入一个中缀表达式，回车表示结束。如果该中缀表达式正确，那么

在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。 d) 测试数据 输入：

21+23*（12-6） 输出：

21 23 12 6 -*+ 二、概要设计 抽象数据类型

为实现上述程序的功能，应以字符串存储用户的输入，以及计算出的结果。 算法的基本思想 根据题目要求，利用二叉树后序遍历来实现表达式的转换。该算法的基本模块包括二叉树的建立以及如何把输入的中缀表达式利用二叉树后序遍历转化为后缀表达式。

1、首先要将输入的中缀表达式（数字字符）存入到二叉树中，由于存在两位或者两位以上的数，甚至还有小数，所以考虑用字符型指针存储数字字符和操作符。

2、为了便于将中缀表达式存入二叉树中，在录入中缀表达式后，要进行相应的处理， 比如去掉空格符，添加结束标志，如‘=’、‘#’等。

3、中缀表达式存入到二叉树的过程中，要注意处理的顺序，如‘+’、‘-’号的优先级比‘*’、‘/’号的 低，当遇到‘*’、‘/’号时，要判断树以上的节点中是否有‘+’、‘-’号，有的话要与其交换位置。遇到‘（’时要反复创建二叉树的结点，构建子二叉树，考虑到括号内要处理的步骤可能会较多，可以考虑用递归。遇到‘）’时则直接结束此子二叉树的建立。此外二叉树中叶子结点存储操作数，非叶子结点存储操作码。

4、对创建好的二叉树进行后序遍历，即可得到相应的后缀表达式，实现方法可以用递归的方式，由于后面还要计算表达式的值，故便利的过程中要将结点中得到的数据存入新的字符数组中。

程序的流程

程序由三个模块组成：

（1） 输入模块：完成一个中缀表达式的输入，存入字符串数组array[Max]中。

（2） 计算模块：设计一个建立二叉树的函数，Node* crtTree(Node* root)，传入根结

点指针，返回根结点指针，该函数的实现还要反复使用另一个函数char getOp(Node *temp)，其将数字字符存入一个结点，并返回数字字符的后一个符

号。void deal()函数功能是对字符数组进行处理。void output(Node *root); 函数功能是获得处理后的字符串，也就是中缀表达式转化为的后缀表达式。

（3） 输出模块：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式和表

达式的值；如果不正确，在字符界面上输出表达式错误提示。

三、详细设计

物理数据类型

2 / 11

数据结构——实验报告

题目要求输入的四则运算表达式运算符只有加减乘除，操作数有整数和小数，为了能够存储，采用C语言中的字符串数组。

char ch[Max]; 算法的时空分析

算法的运行时间主要耗费在二叉树的建立过程中。可以发现，每当遇到一个运算符或操作数时，都要调用一次函数char getOp(Node *temp)，来将其存入二叉树的结点中，其中也会遇到递归的情况，但耗时可以忽略。所以假设输入的字符串中字符个数为N，则算法的时间复杂度为O(N)。

输入和输出的格式 输入

本程序可以将输入的四则运算表达式（中缀表达式）转换为后缀表达式 //提示

请输入四则运算表达式：//提示 等待输入 输出 //提示

后缀表达式为：//输出结果的位置 表达式的值为：//输出结果的位置

四、调试分析 本次实验的难点主要是在建立二叉树的问题上。关于如何把中缀表达式存入二叉树中，我参考了网上的一些方法，成功实现了目标，但是却遇到了一个问题，那就是不能处理小数，甚至两位或两位以上的整数。因为如果采用字符数组来存储操作数，运算符合一位整数还可以处理，但对于两位数就就会出问题，最后我改进采用字符串数组来存储操作数，成功解决了问题。

另外在处理输入的非法表达式问题中，我也费了很大功夫，但总体问题不大。 五、测试结果

六、用户使用说明（可选）

1、本程序的运行环境为DOS操作系统 2、运行程序时

提示输入四则运算表达式

本程序可以将中缀表达式转化为后缀表达式，并计算结果

请输入四则运算表达式： 输出

后缀表达式为：

表达式的值为：

七、附录（可选）

3 / 11

数据结构——实验报告

程序源代码（c++）

1、利用二叉树后序遍历来实现表达式的转换： #include #include #include #include const int Max=100; using namespace std; class Node{ public:

char ch[Max]; //考虑到数值有时会是两位数，所以使用字符串数组 Node* lChild; Node* rChild; Node(){ strcpy(ch,\ lChild=rChild=NULL; } ~Node(){ if(lChild!=NULL) delete lChild; if(rChild!=NULL) delete rChild; } };

static int count=0;

static char array[Max]; //保存原始的中缀表达式

static char str[2*Max]; //保存后序遍历出来的字符串，为表达式求值提供方便 static int k=0;

char getOp(Node *temp); //temp指针保存每个结点，返回的是运算符 Node* crtTree(Node* root); //传入根结点指针，返回根结点指针 void output(Node *root); //获得处理后的字符串 bool isError(char); //判断字符是否有问题 void deal(); //对字符数组进行处理

double value(string); // 计算后缀表达式，得到其结果。

int main(){ Node* root=NULL; cout<<\输入中缀表达式：\ cin.getline(array,40); deal(); root=crtTree(root); cout<<\输出后缀表达式：\ output(root); cout<

4 / 11

数据结构——实验报告

cout<<\输出后缀表达式的值：\ if(value(str)!=0) cout<

//将数字字符存入一个结点，并返回数字字符的后一个符号 char getOp(Node *temp){ int i=0; if( isError(array[count]) ) exit(0); while(array[count]<='9'&&array[count]>='0'||array[count]=='.'){ temp->ch[i]=array[count]; i++; count++; } temp->ch[i]='\\0'; count++; return array[count-1]; }

//传入根结点指针，返回根结点指针 Node* crtTree(Node* root) { Node *p,*q; char op; if(root==NULL){ root=new Node; p=new Node; } op=getOp(root); while(op!='='){ q=new Node; q->ch[0]=op; q->ch[1]='\\0'; switch(op) { case '+': case '-': q->lChild=root; root=q; p=new Node; op=getOp(p); root->rChild=p; break;

5 / 11

数据结构——实验报告

case '*': case '/': if(root->ch[0]=='+'||root->ch[0]=='-'){ p=new Node; strcpy(p->ch,root->ch); p->lChild=root; p->rChild=q; op=getOp(root); root=p; } else { q->lChild=root; root=q; p=new Node; op=getOp(p); root->rChild=p; } break; case '(': p=root; while(p->rChild) p=p->rChild; if(p->lChild==NULL) { p->lChild=crtTree(p->lChild); //递归创建括号里的指针 op=array[count]; count++; break; } else{ p->rChild=crtTree(p->rChild); //递归创建括号里的指针 op=array[count]; count++; break; } case ')': return root; } } return root; }

//传入根结点，后序遍历,赋值给另一个字符数组（主要是为了给后序的计算表达式值提供方便）

void output(Node *root){ int n; if(root){ output(root->lChild); output(root->rChild);

6 / 11

数据结构——实验报告

n=0; while(root->ch[n]!='\\0') str[k++]=root->ch[n++]; str[k++]=' '; } }

bool isError(char ch){ //判断每个字符是否有错 if(ch!='+'&&ch!='-'&&ch!='*'&&ch!='/'&&!(ch<='9'&&ch>='0')&&ch!='.'&&ch!='('&&ch!=')'){ }

cout << \字符错误！\ return true; }

return false;

void deal(){ //对字符数组进行处理 int i=0,n=0; while(array[i]){ if(array[i]==' '||array[i]=='=') i++; array[n++]=array[i++]; } array[n++]='='; array[n]='\\0'; }

double value(string s2){ // 计算后缀表达式，得到其结果。 stack < double> s; double x,y; int i = 0; while(i < s2.length() ){ if(s2[i] == ' ') i++; switch(s2[i]) { case '+': if(s.size()>=2){ x = s.top(); s.pop(); x += s.top(); s.pop(); i++; break; } else return 0; case '-': if(s.size()>=2){ x = s.top(); s.pop(); x =s.top()-x; s.pop(); i++; break; } else return 0;

7 / 11

数据结构——实验报告

case '*': if(s.size()>=2){ x = s.top(); s.pop(); x *= s.top(); s.pop(); i++; break; } else return 0; case '/': if(s.size()>=2){ if( s.top()==0) return 0; else{ x = s.top(); s.pop(); x = s.top()/x; s.pop(); i++; break; } } else return 0; default : x = 0; while('0' <= s2[i]&&s2[i] <= '9'){ x = x*10+s2[i] - '0'; i++; } if(s2[i] == '.'){ double k = 10.0; y = 0; i++; while('0' <= s2[i]&&s2[i] <= '9'){ y += ((s2[i]-'0')/k); i++; k *= 10; } x += y; } break; } if(x!=0) s.push(x); } if( s.size()==1 ) return s.top(); else return 0; }

2、利用堆栈来实现中缀表达式转换为后缀表达式。

8 / 11

数据结构——实验报告

#include #include #include #include using namespace std;

int cmp(char ch){ // 运算符优先级 switch(ch) {

case '+':

case '-': return 1; case '*':

case '/': return 2; default : return 0; } }

void change(string &s1, string &s2){ // 中缀表达式转变后缀表达式 stack s; s.push('#'); int i = 0;

while(i < s1.length()){ //分成四个级别来检验中缀表达式 //s1.length()是为了s1的长度，不包括\\0

if(s1[i] == '(') //级别一 s.push(s1[i++]);

else if(s1[i] == ')'){ //级别二 while( s.top() != '(' ){ s2 += s.top(); s2 += ' '; s.pop(); }

s.pop(); i++; }else if( s1[i] == '+'||s1[i] == '-'||s1[i] == '*'||s1[i] == '/' ){ //级别三 while( cmp(s.top()) >= cmp(s1[i]) ){ s2 += s.top(); s2 += ' '; s.pop(); }

s.push(s1[i]); i++; }

else{ //级别四

while('0' <= s1[i]&&s1[i] <= '9'||s1[i] == '.'){ s2 += s1[i++];

9 / 11

数据结构——实验报告

}

s2 += ' '; } }

while(s.top() != '#'){ //最后一步 s2 += s.top(); s2 += ' '; s.pop(); } }

double value(string &s2){ // 计算后缀表达式，得到其结果。 stack s; double x,y; int i = 0;

while(i < s2.length()-1){ //由于s2的最后一位是空格，影响判断，所以用s2.length()-1

if(s2[i] == ' ') i++; switch(s2[i]) { case '+': if(s.size()>=2){ x = s.top(); s.pop(); x += s.top(); s.pop(); i++; break; } else return 0; case '-': if(s.size()>=2){x = s.top(); s.pop(); x =s.top()-x; s.pop(); i++; break; } else return 0; case '*': if(s.size()>=2){x = s.top(); s.pop(); x *= s.top(); s.pop(); i++; break; } else return 0; case '/': if(s.size()>=2){x = s.top(); s.pop(); x = s.top()/x; s.pop(); i++; break; } else return 0; default : {

x = 0;

while('0' <= s2[i]&&s2[i] <= '9'){ x = x*10+s2[i] - '0'; i++; }

if(s2[i] == '.'){

double k = 10.0; y = 0; i++;

while('0' <= s2[i]&&s2[i] <= '9'){ y += ((s2[i]-'0')/k); i++; k *= 10; }

10 / 11

数据结构——实验报告

x += y; } break; } }

s.push(x); } if( s.size()==1 ) return s.top(); else return 0; }

int main(){

string s1,s2;

cout<<\输入（中缀表达式）：\ cin>>s1; s2=\ change(s1,s2); if(value(s2)){

cout<<\输出1（后缀表达式）：\ cout<

cout<<\输出2（表达式的值）：\

cout<

11 / 11

数据结构——实验报告

x += y; } break; } }

s.push(x); } if( s.size()==1 ) return s.top(); else return 0; }

int main(){

string s1,s2;

cout<<\输入（中缀表达式）：\ cin>>s1; s2=\ change(s1,s2); if(value(s2)){

cout<<\输出1（后缀表达式）：\ cout<

cout<<\输出2（表达式的值）：\

cout<

11 / 11

本文来源：https://www.bwwdw.com/article/fqzp.html