首页 > 代码库 > uva--10700
uva--10700
题意:
输入一串只含有+和*号的表达式,可以通过添加括号来改变表达式的值,求表达式的最大最小值。
思路:
表达式中的数都是不大于20的正整数,由a*b+c<=a*(b+c)可以知道,先算乘法后算加法时表达式的值最小,
先算加法后算乘法时表达式的值最大。
由这个思路,我先把表达式中的运算符和数字都提取出来放在栈中,然后根据两种情况进行计算。
可以写出代码后WA了无数次就是过不了。。。。。。
下面的AC代码是看了别人的题解后模仿写出的,其主要的思路是一样,但是他用数组模拟了栈,
然后直接在从表达式中提取数据的过程中进行了计算;我觉得他思路比较巧妙的一点是,在第一个数字前
就假设了一个运算符,将第一个数字和其他的数字在形式上统一了起来,这样大大的简化了处理过程。
另外这个题目的结果比较大,需要用double类型来保存。
代码如下:
<span style="font-size:18px;">#include<iostream> #include<cstdio> #include<cstring> #include<stack> using namespace std; int main() { int i,j,k,t; char str[100]; double min,max,stack[30]; scanf("%d",&t); while(t--) { scanf("%s",str); i=0; min=0;max=1.0; int top=0; char ch='+'; while(str[i]!='\0') { k=0; while(str[i]>='0'&&str[i]<='9') { k=k*10+str[i]-'0'; i++; } if(ch=='+') stack[++top]=k; else stack[top]*=k; if(str[i]!='\0') ch=str[i++]; } for(i=1;i<=top;i++) min+=stack[i]; top=0; i=0; ch='*'; while(str[i]!='\0') { k=0; while(str[i]>='0'&&str[i]<='9') { k=k*10+str[i]-'0'; i++; } if(ch=='*') stack[++top]=k; else stack[top]+=k; if(str[i]!='\0') ch=str[i++]; } for(i=1;i<=top;i++) max*=stack[i]; printf("The maximum and minimum are %0.lf and %0.lf.\n",max,min); } return 0; } </span>
找不到错误的WA代码如下:
<span style="font-size:18px;">#include<iostream> #include<cstdio> #include<cstring> #include<stack> using namespace std; int main() { char str[10000]; int i,j,k,t; double a[10000]; scanf("%d",&t); while(t--) { stack<double>s1,s2; stack<char>s3,s4; scanf("%s",str); double minnum=0,maxnum=1; int len=strlen(str); k=0; for(i=0;i<len;i++) { k=k*10+str[i]-'0'; if(str[i]=='+'||str[i]=='*') break; } if(i>=len) { printf("The maximum and minimum are %d and %d.\n",k,k); continue; } for(i=0;i<len;i++) { k=0; while(str[i]!='*'&&str[i]!='+'&&i<len) { k=k*10+str[i]-'0'; i++; } s1.push(k); s2.push(k); s3.push(str[i]); s4.push(str[i]); } s3.pop(); s4.pop(); k=0; while(1) { char ch=s3.top(); s3.pop(); if(ch=='*') { int k1=s1.top(); s1.pop(); int k2=s1.top(); s1.pop(); s1.push(k1*k2); } else { a[k++]=s1.top(); s1.pop(); } if(s3.empty()) { a[k++]=s1.top(); s1.pop(); break; } } for(i=0;i<k;i++) minnum+=a[i]; k=0; while(1) { char ch=s4.top(); s4.pop(); if(ch=='+') { int k1=s2.top(); s2.pop(); int k2=s2.top(); s2.pop(); s2.push(k1+k2); } else { a[k++]=s2.top(); s2.pop(); } if(s4.empty()) { a[k++]=s2.top(); s2.pop(); break; } } for(i=0;i<k;i++) maxnum*=a[i]; printf("The maximum and minimum are %0.lf and %0.lf.\n",maxnum,minnum); } return 0; } </span>
uva--10700
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。