题意:
输入一串仅仅含有+和*号的表达式,能够通过加入括号来改变表达式的值,求表达式的最大最小值。
思路:
表达式中的数都是不大于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>