2014牡丹江现场赛水题

给出波兰式，推断其是否合法。假设不合法有两种操作：

1：任何位置加一个数字或者操作符

2：随意两个位置的元素对调

贪心模拟就可以

先推断数字数是否大于操作符数，若不大于 ans+=sum2-sum1+1；新增加的数字所有放到左端。

然后从左到右遍历一遍。存储到当前位置为止，数字数和sum1。和操作数和sum2

若sum2>=1sum1。优先与队尾的数字对调，若没有则sum1++，表示在最左端加一个数字

#include "stdio.h"

#include "string.h"

int main()

{

    int n,sum1,sum2,i,len,ans,j,ok;

    char str[1010];

    scanf("%d",&n);

    while (n--)

    {

        scanf("%s",str);

        sum1=sum2=0;

        len=strlen(str);

        for (i=0;str[i];i++)

            if (str[i]=='*') sum2++;

            else sum1++;

        if (sum2==0)

        {

            printf("0\n");

            continue;

        }

        if (sum1==0)

        {

            printf("%d\n",sum2+1);

            continue;

        }

        ans=0;

        if (sum1<=sum2)

        {

            ans+=sum2-sum1+1;

            sum2=0;

            sum1=ans;

        }

        else sum1=sum2=0;

        for (i=0;str[i];i++)

        {

            if (str[i]<='9' && str[i]>='1') {sum1++; continue;}

            if (str[i]=='*') sum2++;

            if (sum1>sum2) continue;

            else

            {

                ok=0;

                for (j=len-1;j>i;j--)

                    if(str[j]<='9' && str[j]>='1')

                    {

                        ans++;

                        sum1++;

                        sum2--;

                        str[j]='*';

                        ok=1;

                        break;

                    }

                if (ok==0)

                {

                    if (i==0)

                    {

                        ans+=2;

                        sum1+=2;

                    }

                    else

                    {

                        ans++;

                        sum1++;

                    }

                }

            }

        }

        if (str[len-1]!='*') ans++;

        printf("%d\n",ans);

    }

    return 0;

}