首页 > 代码库 > 表达式求值 数据结构
表达式求值 数据结构
数据结构中栈的应用
1 #include<iostream> 2 #include<cstring> 3 4 using namespace std; 5 6 char str[1000]; 7 char ans[1000]; 8 struct fu 9 { 10 char ff[1000]; 11 int top; 12 }fse; 13 struct data 14 { 15 int da[1000]; 16 int top; 17 }dse; 18 int you(char a) 19 { 20 switch(a) 21 { 22 case ‘#‘:return -1; 23 case ‘(‘: return 0; 24 case ‘*‘: 25 case ‘/‘: return 2; 26 case ‘+‘: 27 case ‘-‘: return 1; 28 default: return -3; 29 } 30 } 31 void tran() 32 { 33 int cont=strlen(str); 34 str[cont]=‘#‘; 35 int pos=0; 36 fse.top=0; 37 for(int i = 0; i <= cont; ) 38 { 39 int flag=0; 40 while(str[i]>=‘0‘ && str[i]<=‘9‘) 41 { 42 if(pos&&ans[pos-1]!=‘ ‘&&(ans[pos-1]<‘0‘||ans[pos-1]>‘9‘)) 43 ans[pos++]=‘ ‘; 44 ans[pos++]=str[i]; 45 flag=1; 46 i++; 47 } 48 if(flag) 49 ans[pos++]=‘ ‘; 50 if(str[i]==‘)‘) 51 { 52 while(fse.ff[fse.top-1]!=‘(‘) 53 ans[pos++]=fse.ff[--fse.top]; 54 fse.top--; 55 } 56 else 57 if(you(str[i])==-1) 58 { 59 while(fse.top) 60 { 61 ans[pos++]=fse.ff[--fse.top]; 62 } 63 } 64 else 65 if(fse.top==0) 66 fse.ff[fse.top++]=str[i]; 67 else 68 if(you(str[i])==0) 69 fse.ff[fse.top++]=str[i]; 70 else 71 { 72 if(you(str[i])>you(fse.ff[fse.top-1])) 73 fse.ff[fse.top++]=str[i]; 74 else 75 if(you(str[i]<=you(fse.ff[fse.top-1]))) 76 { 77 while(fse.top && you(str[i]<=you(fse.ff[fse.top-1]))) 78 ans[pos++]=fse.ff[fse.top-1],fse.top--; 79 fse.ff[fse.top++]=str[i]; 80 } 81 } 82 i++; 83 } 84 ans[pos]=0; 85 } 86 int read(int i) 87 { 88 int x=0; 89 while(ans[i]>=‘0‘&&ans[i]<=‘9‘) 90 x=x*10+(ans[i]-‘0‘),i++; 91 dse.da[dse.top++]=x; 92 return i; 93 } 94 int post() 95 { 96 dse.top=0; 97 int cont = strlen(ans); 98 for(int i = 0; i < cont;) 99 { 100 if(ans[i]>=‘0‘&&ans[i]<=‘9‘) 101 i=read(i); 102 else if(ans[i]==‘+‘) 103 dse.da[dse.top-2]+=dse.da[dse.top-1],dse.top--; 104 else if(ans[i]==‘-‘) 105 dse.da[dse.top-2]-=dse.da[dse.top-1],dse.top--; 106 else if(ans[i]==‘*‘) 107 dse.da[dse.top-2]*=dse.da[dse.top-1],dse.top--; 108 else if(ans[i]==‘/‘) 109 dse.da[dse.top-2]/=dse.da[dse.top-1],dse.top--; 110 i++; 111 if(ans[i]==‘ ‘) 112 i++; 113 114 } 115 return dse.da[0]; 116 } 117 int main() 118 { 119 while(cin>>str) 120 { 121 tran(); 122 cout<<post()<<endl; 123 } 124 return 0; 125 }
表达式求值 数据结构
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。