编译原理中表达式求值，是用栈还是用二叉树？
如题，有点忘记了。
依稀记得是用逆波兰式然后用两个栈，一个保存操作符一个保存操作数。但是好像在ＡＮＴＬＲ这种工具中是先变成语法树？
是直接扫描表达式的时候就改成逆波兰式压栈完全不用语法树？
还是先生成语法树然后后序遍历获得逆波兰式？
[解决办法]
用栈用数就可以解决。
[解决办法]
逆波兰
[解决办法]
不管是RR文法还是LR文法，都是用栈实现吧，只不过逻辑上是一棵树
[解决办法]
栈模拟 或 表达式树
[解决办法]
中缀到后缀
#include<iostream>#include<string>#include<map>#include<utility>#include<stack>using namespace std;map<char,int> ope;int getNumber(const string& str,int& pos){ int val=0; int l=str.length(); while(pos<l&&str[pos]<='9'&&str[pos]>='0'){ val*=10; val+=str[pos]-'0'; ++pos; } return val;}int calculator(const string& str){ stack<char> sta_ope; string postfix=""; int pos=0,l=str.length(); bool isNumber=(str[0]>='0'&&str[0]<='9'?true:false); while(pos<l){ switch(str[pos]){ case '(': sta_ope.push('('); isNumber=false; break; case ')': while(sta_ope.top()!='('){ postfix+=" "; postfix+=sta_ope.top(); sta_ope.pop(); } sta_ope.pop(); isNumber=false; break; case '+': case '-': case '*': case '/': while(!sta_ope.empty()&&sta_ope.top()!='('&&ope[sta_ope.top()]>=ope[str[pos]]){ postfix+=" "; postfix+=sta_ope.top(); sta_ope.pop(); } sta_ope.push(str[pos]); isNumber=false; break; default: if(str[pos]>='0'&&str[pos]<='9'){ if(!isNumber) postfix+=" "; postfix+=str[pos]; isNumber=true; } else return -1; } ++pos; } while(!sta_ope.empty()){ postfix+=" "; postfix+=sta_ope.top(); sta_ope.pop(); } stack<int> sta_num; pos=0,l=postfix.length(); int a,b; while(pos<l){ switch(postfix[pos]){ case '+': a=sta_num.top(); sta_num.pop(); b=sta_num.top(); sta_num.pop(); sta_num.push(b+a); break; case '-': a=sta_num.top(); sta_num.pop(); b=sta_num.top(); sta_num.pop(); sta_num.push(b-a); break; case '*': a=sta_num.top(); sta_num.pop(); b=sta_num.top(); sta_num.pop(); sta_num.push(b*a); break; case '/': a=sta_num.top(); if(a==0)return -1; sta_num.pop(); b=sta_num.top(); sta_num.pop(); sta_num.push(b/a); break; case ' ': break; default: int n=getNumber(postfix,pos); sta_num.push(n); } ++pos; } return sta_num.top();}int main(){ ope.insert(make_pair('+',1)); ope.insert(make_pair('-',1)); ope.insert(make_pair('*',2)); ope.insert(make_pair('/',2)); ope.insert(make_pair('(',3)); string str="(12-(2/(2/2)+2*4))/2-10"; cout<<calculator(str)<<endl; return 0;}
[解决办法]
/*表达树形式，只不过树用的数组形式表示*/#include<iostream>#include<cstring>using namespace std;const int MAX=1000;int lchild[MAX],rchild[MAX];char ope[MAX];int data[MAX];int count=0;bool isPureData(const string& str,int from,int to,int& data){ data=0; for(int i=from;i<to&&str[i]<='9'&&str[i]>='0';++i){ data*=10; data+=str[i]-'0'; } return i==to;}int build_tree(const string& str,int from,int to){ int p=0,f1=-1,f2=-1; int da; if(isPureData(str,from,to,da)){ int n=count++; lchild[n]=-1,rchild[n]=-1; data[n]=da; return n; } int t=from; while(t<to){ switch(str[t]){ case '(': --p; break; case ')': ++p; break; case '+': case '-': if(!p)f1=t; break; case '*': case '/': if(!p)f2=t; break; } ++t; } if(f1<0)f1=f2; if(f1<0) return build_tree(str,from+1,to-1);//( ) int lch=build_tree(str,from,f1); int rch=build_tree(str,f1+1,to); int n=count++; lchild[n]=lch; rchild[n]=rch; ope[n]=str[f1]; return n;}int val(int pos){ if(lchild[pos]==-1) return data[pos]; int a=val(lchild[pos]); int b=val(rchild[pos]); switch(ope[pos]){ case '+': return a+b; break; case '-': return a-b; break; case '*': return a*b; break; case '/': if(b==0)return -1; return a/b; break; }}int calculator(const string& str,int l){ count=0; build_tree(str,0,l); return val(count-1);}int main(){ string str="(12-(2/(2/2)+2*4))/2-10"; cout<<calculator(str,str.length())<<endl; return 0;}
[解决办法]
和语法结合就应该加到语法树里面。 这样遍历时直接就可以知道求值顺序了
如果是纯表达式，编译时可求出的用栈肯定简单些。