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

数据结构——实验报告

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); } …… 此处隐藏：1095字，全部文档内容请下载后查看。喜欢就下载吧 ……