编译原理中表达式求值，是用栈还是用二叉树？
依稀记得是用逆波兰式然后用两个栈，一个保存操作符一个保存操作数。但是好像在ＡＮＴＬＲ这种工具中是先变成语法树？
是直接扫描表达式的时候就改成逆波兰式压栈完全不用语法树？
还是先生成语法树然后后序遍历获得逆波兰式？
12 个解决方案
#1
用树吧
#2
用两个栈，一个保存操作符一个保存操作数
数据结构中有
数据结构中有
#3
用栈用数就可以解决。
#4
逆波兰
#5
不管是RR文法还是LR文法，都是用栈实现吧，只不过逻辑上是一棵树
#6
栈模拟 或 表达式树
#7
中缀到后缀
#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;
}
#8
/*表达树形式，只不过树用的数组形式表示*/
#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;
}
#9
用栈实现
#10
用栈实现很方便
#11
用栈实现，你不觉得树有些太庞大了嘛
#12
和语法结合就应该加到语法树里面。 这样遍历时直接就可以知道求值顺序了
如果是纯表达式，编译时可求出的用栈肯定简单些。
如果是纯表达式，编译时可求出的用栈肯定简单些。
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。