UVALive 2056 Lazy Math Instructor（递归处理嵌套括号）

　　因为这个题目说明了优先级的规定，所以可以从左到右直接运算，在处理嵌套括号的时候，可以使用递归的方法，给定每一个括号的左右边界，伪代码如下：

int Cal（）{

if(括号) sum += Cal();

　　　else sum += num;

　　return sum;

}

　　但是这个题目着实坑了我一下，见过WA了，没见过TLE呢……我因为没有看到有空格这个条件，无线TLE，又是消除函数又是改用数组模拟栈，其实就是读入出错和忘记了处理空格，改了之后，成功AC了。代码如下：

#include<iostream>

#include<cmath>

#include<vector>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<stack>

using namespace std;

#define maxn 100

int pos[maxn],st[maxn];

int Cal(int id,const char *a){

    int sum = ,tmp;

    for(int i = id+;i < pos[id];i++){

        if(a[i] == '('){

            tmp = Cal(i,a);

            if(a[i-]=='(' || a[i-]=='+') sum += tmp;

            else if(a[i-]=='-') sum -= tmp;

            else if(a[i-]=='*') sum *= tmp;

            i = pos[i];

        }

        else if((a[i]>='a'&&a[i]<='z')||(a[i]>=''&&a[i]<='')){

            if(a[i]>='a'&&a[i]<='z') tmp = (a[i]-'a'+);

            else tmp = a[i]-'';

            if(a[i-]=='(' || a[i-]=='+') sum += tmp;

            else if(a[i-]=='-') sum -= tmp;

            else if(a[i-]=='*') sum *= tmp;

            i++;

        }

    }

    return sum;

}

int getnum(const char *a){

    memset(pos,,sizeof(pos));

    memset(st,,sizeof(st));

    int len = strlen(a);

    int top = ;

    for(int i = ;i < len;i++)

    {

        if(a[i]=='(') st[top++] = i;

        if(a[i]==')') {

            pos[st[--top]] = i;

        }

    }

    int sum = ,tmp;

    for(int i = ;i < len;i++){

        if(a[i]=='('){

            tmp = Cal(i,a);

            if(i ==  || a[i-]=='+')

            sum += tmp;

            else if(a[i-] == '-')  sum -= tmp;

            else if(a[i-] == '*')  sum *= tmp;

            i = pos[i];

        }

        else if((a[i]>='a'&&a[i]<='z')||(a[i]>=''&&a[i]<='')){

            if(a[i]>='a'&&a[i]<='z') tmp = (a[i]-'a'+);

            else tmp = a[i]-'';

            if(i ==  || a[i-]=='+')

            sum += tmp;

            else if(a[i-] == '-')  sum -= tmp;

            else sum *= tmp;

            i++;

        }

    }

    //printf("the num = %d\n",sum);

    return sum;

}

int main()

{

    int t,lena,lenb,num1,num2,tot;

    char a[maxn],b[maxn];

    scanf("%d",&t);

    getchar();

    while(t--){

        gets(a);

        lena = strlen(a);

        tot = ;

        for(int i = ;i < lena;i++){

            if(a[i]==' ') continue;

            else b[tot++] = a[i];

        }

        b[tot] = '\0';

        num1 = getnum(b);

        gets(a);

        lena = strlen(a);

        tot = ;

        for(int i = ;i < lena;i++){

            if(a[i]==' ') continue;

            else b[tot++] = a[i];

        }

        b[tot] = '\0';

        num2 = getnum(b);

        if(num1 == num2) puts("YES");

        else puts("NO");

    }

    return ;

}

巴特西

UVALive 2056 Lazy Math Instructor（递归处理嵌套括号）

最新文章

热门文章