2

我是使用 C 解决问题的新手，我正在尝试解决 复杂表达式上的 SPOJ 问题

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void removeBrackets(char *string , int position1 , int position2);
int main()
{
char exp[]="(a+b)-(c-d)-(e/f)";
char ops[]={'/','*','+','-','(',')','\0'};
char found[50][5];
int stack[3];
int i,j , k =0;

int l = (int)strlen(exp);
int lExp = l ;
char *p = exp ;

//    //remove external brackets
//    while (*(p+0)=='(' && *(p+strlen(p)-1)==')')
//        removeBrackets(exp, 0, ((int)strlen(p)-1));



printf("expression : %s\n",exp);
printf("operators : %s\n",ops);

//find the operators and their location
l = 0 ; 
for(i=0;i<lExp;i++)
{
    for(j=0;j<strlen(ops);j++)
    {
        if(exp[i]==ops[j])
        {
            found[l][2]='N';

            found[l][0]=i;
            found[l][1]=ops[j];
            if (exp[i-2]=='(' && exp[i+2]==')')
            {
                found[l][2]='Y';
                found[l][3]=exp[i-3];
                found[l][4]=exp[i+3];
            }
            if (found[l][1]=='(')
            {
                stack[k] = found[l][0];
                k++;
            }
            else if(found[l][1]==')')
            {
                stack[k] = found[l][0];
                if (stack[0] == 0 && stack[1] == lExp-1)
                {
                    removeBrackets(exp, 0, (int)strlen(exp)-1);
                    break ;
                }
                removeBrackets(exp, stack[k-1], stack[k]);

                //stack[k] = -1 ;
                //stack[k-1] = -1 ;
                k--;
            }
            printf("found '%c' at '%d' and within brackets: %c\n",found[l][1],found[l][0],found[l][2]);
            l++;
        }
    }
}

   //find where brackets are the corresponding sign in the brackets
    for (i=0; i<l-1; i++)
    {
        if(found[i][2]=='Y')
        {
            //find higher precedence operators present nearby , and if their precedence is lower , then remove the brackets ,else keep the brackets


            //1-find the operator inside the brackets
            switch (found[i][1])
            {
                case '/':
                    printf("\nfound '/' within brackets");
                    removeBrackets(exp, found[i][0]-2, found[i][0]+2);
                    //remove the brackets
                    break;
                case '*':
                    printf("\nfound '*' within brackets");
                    if (found[i][3] == '/' || found[i][4] == '/')
                        break ;
                    else
                        removeBrackets(exp, found[i][0]-2, found[i][0]+2);

                    break;
                case '+':
                    printf("\nfound '+' within brackets");
                    if (found[i][3] == '/' || found[i][4] == '/' || found[i][3] == '*' || found[i][4] == '*' )
                        break ;
                    else
                        removeBrackets(exp, found[i][0]-2, found[i][0]+2);


                    break;
                case '-':
                    printf("\nfound '-' within brackets");
                    if (found[i][3] == '/' || found[i][4] == '/' || found[i][3] == '*' || found[i][4] == '*' || found[i][4] == '+' || found[i][3] == '+')
                        break ;
                    else
                        removeBrackets(exp, found[i][0]-2, found[i][0]+2);
                                            break;

                default:
                    break;
            }

        }
    }
printf("\nstring modified : %s",exp);

 }

 void removeBrackets(char *string, int position1 , int position2)
 {
char *p = string;
char *newString = (char *)malloc(strlen(string -1));
int i = 0 , j =0 ;
for (i = 0 ; i <strlen(string); i++)
{
    if (i == position1 || i == position2)
        continue ;
    else
    {
        newString[j] = *(p+i);
        j++ ;
    }
}
newString[j]='\0';
strcpy(string, newString);
printf("\n-----after removing brackets :- %s\n",newString);
free(newString);
 }

我正在做的是，扫描所有单词，然后将找到的运算符和括号存储在数组'Found'中，堆栈是一个数组来检查'（'和'）'的序列，'ops'是一个要存储的数组所有可能的运算符和括号，然后，如果在括号内找到运算符，则根据左右运算符的优先级，括号被删除。

但是，在尝试了很多之后，我无法为所有测试用例提出删除括号的解决方案。我在互联网上搜索，他们已经使用树来解决这个问题。任何人都可以建议对我的代码进行一些更改以解决问题..？？还是说，没有树就无法解决问题？？

4

0 回答 0