表达式求值、表达式转二叉树
<div id="cnblogs_post_body">1、后序表达式求值：后续表达式(逆波兰式)的特点：没有括号。
求值方法：
从前向后扫，
遇到操作数压栈；
遇到操作符，从栈中取出2个操作数运算，结果压栈。
最终栈中所剩的数为结果。
2、中序表达式求值
我们先来定义运算符的优先级：
(
+,-
*,/,%
从上到下依次升高
准备2个栈，一个专门存放运算符，另一个专门存放操作数。
1.遇到)，那么退栈计算到(为止.结果压栈。
2.遇到运算数.那么压栈。
3.如果当前运算符优先级低于栈顶运算符.那么计算栈顶运算符并将结果压栈.
4.否则压栈.
计算带括号和浮点数的表达式：
<div class="cnblogs_code" >http://images.cnblogs.com/OutliningIndicators/ContractedBlock.gifhttp://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gifView Code <div id="cnblogs_code_open_65623b2f-502e-4e90-87a9-78ebf6bb42da" class="cnblogs_code_hide">#include<iostream> #include<stack> #include<string> #include<cctype> using namespace std; typedef string::size_type it; char Compare(char op,char ch) //优先级比较 { if((op=='#'&&ch=='#')||(op=='('&&ch==')')) return '='; if(ch=='#') return '<'; if(op=='#') return '>'; if(op=='(') return '>'; if(ch==')') return '<'; if(ch=='(') return '>'; if(ch=='*'||ch=='/') if(op=='+'||op=='-') return '>'; else return '<'; if(ch=='+'||ch=='-') return '<'; } void modify(string& s) //优化表达式 { string s1="()+-*/"; for(it i=0;i<s.size();++i) { if(isspace(s)) s.erase(i,1); if(!isdigit(s)&&s!='.'&&s1.find(s)==string::npos) s.erase(i,1); if(s=='('&&s1]=='-') s.insert(i+1,"0"); if(i==0&&s=='-') s.insert(i,"0"); } } bool check(const string & s) //检验输入表达式 { string s1="()+-*/"; string s2="+-*/"; stack<char> ch; bool valid=true; for(it i=0;i<s.size();++i) { if(i==0 && s1.find(s,1)!=string::npos) return false; switch(s) { case '(': if(s1.find(s1],1)!=string::npos) return false; break; case ')': if(s2.find(s1])!=string::npos) return false; break; case '+': case '-': case '*': case '/': if(s2.find(s1])!=string::npos) return false; break; } if (s=='(') ch.push(s); if (s==')') if (ch.empty()) { valid=false; break; } else { char b=ch.top(); ch.pop(); if (b=='(') valid=true; else valid=false; } } if (!ch.empty()) valid=false; return valid; } void Calculate(stack<double>& num,stack<char>& ops,const string & s) { string s1="()+-*/#"; it i=0; while(i<s.size()) { it j=s.find_first_of(s1,i); if(j!=string::npos) { if(j!=i) { string s2=s.substr(i,j-i); double n=atof(s2.c_str()); num.push(n); } char ch=s; char op=ops.top(); if(Compare(op,ch)=='>') ops.push(ch); else if(Compare(op,ch)=='=') ops.pop(); else { while(1) { char c=ops.top(); if(Compare(c,ch)=='>') { ops.push(ch); break; } else if(Compare(c,ch)=='=') { ops.pop(); break; } else { char optr=ops.top(); ops.pop(); double n1=num.top(); num.pop(); double n2=num.top(); num.pop(); double value; if(optr=='+') value=n2+n1; if(optr=='-') value=n2-n1; if(optr=='*') value=n2*n1; if(optr=='/') { double E=0.00001; if( n1>-E && n1<E ) { cout<<"Can't evaluate the expression !"; exit(1); } else value=n2/n1; } num.push(value); } } } } i=j+1;//更新i的值 } } int main() { stack <double> num; stack <char> ops; ops.push('#'); string s; cout<<"Input the string:"<<endl; getline(cin,s); modify(s); while(!check(s)) { cout<<"The string is not valid. Input it again! "<<endl; getline(cin,s); modify(s); } cout<<s<<endl; s=s+"#"; Calculate(num,ops,s); cout<<"The result is "<<num.top(); return 0; }
页:
[1]