问题 D: 计算
时间限制: 1 Sec 内存限制: 128 MB
提交: 61 解决: 27
[提交][状态][讨论版][命题人: 外部导入]题目描述
小明在你的帮助下，破密了Ferrari设的密码门，正要往前走，突然又出现了一个密码门，门上有一个算式，其中只有“(”，“)”，“0-9”，“+”，“-”，“*”，“/”，“^”求出的值就是密码。小明数学学得不好，还需你帮他的忙。(“/”用整数除法，取商)
输入
输入共1行，为一个算式。
输出
输出共1行，就是密码。
样例输入
1+(3+2)*(7^2+6*9)/(2)样例输出
258提示
100%的数据满足：算式长度<=30 其中所有数据在2的31次方-1的范围内。
还没学数据结构，听学过的大佬说做法是，开两个栈，一个存运算顺序，一个存数字。具体不太清楚。。。。。
这一题我的方法是模拟人脑运算，优先寻找（），其次^，然后*/，最后+-。前面的遇到一个算一个，然后把式子在字符串中抹去，替代为刚刚算出的值，然后循环计算，直到没有数字以外的符号，就可以退出循环了。。我大体思路是这样。下面附上我的代码。
1 #include <iostream> 2 #include<stack> 3 #include<map> 4 #include<string> 5 using namespace std; 6 stack<int> sta; 7 pair <pair <int,int>,pair <int,int> > f(string& s,int l){ 8 int i=1,a,b; 9 while(s[l-i]<='9'&&s[l-i]>='0'){ 10 if(l-i==0){ 11 break; 12 13 } 14 15 i++; 16 17 } 18 if(l-i!=0) 19 i--; 20 int start=l-i; 21 string st=s.substr(start,i); 22 a=atoi(st.c_str()); 23 i=1; 24 while(s[l+i]<='9'&&s[l+i]>='0'){ 25 i++; 26 if(l+i==s.size()) 27 break; 28 } 29 st=s.substr(l+1,i-1); 30 b=atoi(st.c_str()); 31 int en=l+i-1; 32 33 34 35 pair <pair <int,int>,pair <int,int> > p(make_pair(a,b),make_pair(start,en)); 36 return p; 37 } 38 39 40 int val(string &s){ 41 int sum=0; 42 int l; 43 while((l=s.find("^"))!=string::npos){ 44 pair <pair <int,int>,pair <int,int> > p=f(s,l); 45 int cj=1; 46 int a=p.first.first,b=p.first.second; 47 for(int i=0;i<b;i++) 48 cj*=a; 49 s.erase(p.second.first,p.second.second-p.second.first+1); 50 s.insert(p.second.first,to_string(cj)); 51 52 } 53 for(int i=0;i<s.size();i++){ 54 if(s[i]=='*'||s[i]=='/'){ 55 pair <pair <int,int>,pair <int,int> > p=f(s,i); 56 int cj=1; 57 int a=p.first.first,b=p.first.second; 58 if(s[i]=='*') 59 cj=a*b; 60 else 61 cj=a/b; 62 63 s.erase(p.second.first,p.second.second-p.second.first+1); 64 s.insert(p.second.first,to_string(cj)); 65 i=0; 66 } 67 68 } 69 for(int i=0;i<s.size();i++){ 70 if(s[i]=='+'||s[i]=='-'){ 71 pair <pair <int,int>,pair <int,int> > p=f(s,i); 72 int cj=1; 73 int a=p.first.first,b=p.first.second; 74 if(s[i]=='+') 75 cj=a+b; 76 else 77 cj=a-b; 78 s.erase(p.second.first,p.second.second-p.second.first+1); 79 s.insert(p.second.first,to_string(cj)); 80 i=0; 81 } 82 83 84 } 85 return atoi(s.c_str()); 86 87 } 88 89 int main(int argc, char *argv[]) 90 { 91 string s; 92 int i=0; 93 getline(cin,s); 94 while(i!=s.size()){ 95 if(s[i]=='(') 96 sta.push(i); 97 if(s[i]==')'){ 98 if(!sta.empty()){ 99 string vs=s.substr(sta.top()+1,i-sta.top()-1); 100 string v=to_string(val(vs)); 101 s.erase(sta.top(),i-sta.top()+1); 102 s.insert(sta.top(),v); 103 sta.pop(); 104 i=-1; 105 while(!sta.empty()) 106 sta.pop(); 107 108 109 } 110 else{ 111 printf("Wrong\n"); 112 return 0; 113 } 114 } 115 i++; 116 117 } 118 if(!sta.empty()){ 119 printf("Wrong\n"); 120 return 0; 121 } 122 else{ 123 int sum=val(s); 124 printf("%d\n",sum); 125 126 } 127 128 129 }
这是我的代码。
然后我们来看看大佬的代码。。。。
1 #include<iostream> 2 #include <stack> 3 #include<string.h> 4 #include<math.h> 5 #include<cstdio> 6 using namespace std; 7 int mypow(int a,int b) 8 { 9 int c=1; 10 for(int i=0;i<b;i++) 11 { 12 c=c*a; 13 } 14 return c; 15 } 16 int main() 17 { 18 char c; 19 char s[300]; 20 gets(s); 21 int w=strlen(s); 22 for(int i=w;i>=1;i--) 23 { 24 s[i]=s[i-1]; 25 } 26 s[w+1]=')'; 27 s[0]='('; 28 s[w+2]='\0'; 29 stack<int> num; 30 stack<char> op; 31 for(int i=0;i<strlen(s);i++) 32 { 33 int f=0; 34 int d=0; 35 if(isdigit(s[i])) 36 { 37 d=s[i]-'0'; 38 f=1; 39 while(isdigit(s[i+1])) 40 { 41 f=1; 42 d=d*10+s[i+1]-'0'; 43 i++; 44 } 45 } 46 if(f) 47 { 48 num.push(d); 49 } 50 if(s[i]=='+'||s[i]=='-') 51 { 52 while(!op.empty()&&(op.top()=='*'||op.top()=='/'||op.top()=='^'||op.top()=='+'||op.top()=='-')) 53 { 54 if(op.top()=='+') 55 { 56 int a=num.top(); 57 num.pop(); 58 int b=num.top(); 59 num.pop(); 60 num.push(a+b); 61 } 62 if(op.top()=='-') 63 { 64 int a=num.top(); 65 num.pop(); 66 int b=num.top(); 67 num.pop(); 68 num.push(b-a); 69 } 70 if(op.top()=='*') 71 { 72 int a=num.top(); 73 num.pop(); 74 int b=num.top(); 75 num.pop(); 76 num.push(a*b); 77 } 78 if(op.top()=='/') 79 { 80 int a=num.top(); 81 num.pop(); 82 int b=num.top(); 83 num.pop(); 84 num.push(b/a); 85 } 86 if(op.top()=='^') 87 { 88 int a=num.top(); 89 num.pop(); 90 int b=num.top(); 91 num.pop(); 92 num.push(mypow(b,a)); 93 } 94 op.pop(); 95 } 96 op.push(s[i]); 97 } 98 if(s[i]=='*'||s[i]=='/') 99 { 100 while(!op.empty()&&(op.top()=='*'||op.top()=='/'||op.top()=='^')) 101 { 102 if(op.top()=='*') 103 { 104 int a=num.top(); 105 num.pop(); 106 int b=num.top(); 107 num.pop(); 108 num.push(a*b); 109 } 110 if(op.top()=='/') 111 { 112 int a=num.top(); 113 num.pop(); 114 int b=num.top(); 115 num.pop(); 116 num.push(b/a); 117 } 118 if(op.top()=='^') 119 { 120 int a=num.top(); 121 num.pop(); 122 int b=num.top(); 123 num.pop(); 124 num.push(mypow(b,a)); 125 } 126 op.pop(); 127 } 128 op.push(s[i]); 129 } 130 if(s[i]=='(') 131 op.push(s[i]); 132 if(s[i]=='^') 133 { 134 while(!op.empty()&&op.top()=='^') 135 { 136 int a=num.top(); 137 num.pop(); 138 int b=num.top(); 139 num.pop(); 140 num.push(mypow(b,a)); 141 op.pop(); 142 } 143 op.push(s[i]); 144 } 145 if(s[i]==')') 146 { 147 while(op.top()!='(') 148 { 149 if(op.top()=='*') 150 { 151 int a=num.top(); 152 num.pop(); 153 int b=num.top(); 154 num.pop(); 155 num.push(a*b); 156 } 157 if(op.top()=='/') 158 { 159 int a=num.top(); 160 num.pop(); 161 int b=num.top(); 162 num.pop(); 163 num.push(b/a); 164 } 165 if(op.top()=='^') 166 { 167 int a=num.top(); 168 num.pop(); 169 int b=num.top(); 170 num.pop(); 171 num.push(mypow(b,a)); 172 } 173 if(op.top()=='+') 174 { 175 int a=num.top(); 176 num.pop(); 177 int b=num.top(); 178 num.pop(); 179 num.push(b+a); 180 } 181 if(op.top()=='-') 182 { 183 int a=num.top(); 184 num.pop(); 185 int b=num.top(); 186 num.pop(); 187 num.push(b-a); 188 } 189 op.pop(); 190 } 191 op.pop(); 192 } 193 } 194 cout<<num.top()<<endl; 195 }
恩，大佬写的代码比较简洁。。。虽然我也还没仔细看。但足以看出大佬与我们的不同。。。
这些代码长度都不短，是否又有更快的方法？
有，但是就并非模拟了，考虑一下python的eval
1 print(eval(input().replace('^','**').replace('/','//')))
一行简洁明了。