Может кто-нибудь сказать мне, каков наилучший выбор структуры данных для решения проблемы @ http://acm.timus.ru/problem.aspx?space=1&num=1027.
Скопировано здесь для справки.
Задача
Текст правильной программы на D ++ содержит символьную часть, арифметику
выражения и комментарии. Комментарии могут появляться везде и могут
содержать любые символы. Комментарий всегда открывается парой символов
(* и закрывается парой символов *) Каждый комментарий должен быть
закрыто. Арифметическое выражение в D ++ всегда открывается "(", является
закрыто ")" и может содержать только символы "= + - / 0123456789) (" и
символы "конец строки". Арифметическое выражение не может начинаться с
пара символов "(". Вы можете наткнуться на встроенные скобки в
арифметическое выражение. В этом случае эти скобки должны быть сбалансированы.
Это означает, что "((1)))", а также "(23)) ((+)" не верны
арифметические выражения. Арифметическое выражение является правильным, если и
только если скобки размещены правильно. Наконец, все остальные
текст программы (результат отклонения всех комментариев и арифметики
выражения из исходного текста программы) может содержать каждый
символ, исключающий "(" и ")". Мы хотели бы особенно отметить, что
пробелы возможны в любом месте текста программы, кроме случаев, когда
появляются в арифметических выражениях.
Будет ли полезно хеширование?
Мой подход такой, как показано ниже (все еще есть некоторые ошибки, сконцентрируйтесь на части DS)
#include <stdio.h>
/* enable to get debug print statements */
#define DEBUG_ENABLE 0
#define INSUFFICIENT_BUFFER -1
#define BUFSIZE 20
char buf[BUFSIZE];/*buffer for ungetch*/
int bufp=0;/*next free position in buf*/
/*get a(possibly pushed-back)character*/
int mygetch(FILE *infile)
{
return(bufp>0)? (buf[--bufp]): (getc(infile));
}
/*push a character back on input*/
int ungetch(char c)
{
if(bufp >= BUFSIZE)
{
printf("ungetch:too many characters - increase the stack buffer size\n");
return INSUFFICIENT_BUFFER;
}
else
{
buf[bufp++]=c;
return 0;
}
}
enum CharType
{
isAlphabet=0,
isNumber,
isSpace,
isNewline,
isOperator,
isOpeningBrace,
isClosingBrace,
isStar,
isOther
};
enum
{
False=0,
True
};
/* return different codes for different types of input characters*/
int getCharType(char ch)
{
if((ch>='A'&&ch<='Z') || (ch>='a'&&ch<='z'))
{
return isAlphabet;
}
else if(ch=='+'||ch=='-'||ch=='/'||ch=='=')
{
return isOperator;
}
else if(ch>='0'&& ch<='9')
{
return isNumber;
}
else if(ch=='*')
{
return isStar;
}
else if(ch=='(')
{
return isOpeningBrace;
}
else if(ch==')')
{
return isClosingBrace;
}
else if(ch==' ')
{
return isSpace;
}
else
{
return isOther;
}
}
int parseInputFile(FILE *infile)
{
int ArthExpScanning = 0;
int CmmntScanning = False;
int ch,chtmp;
while((ch=mygetch(infile))!=EOF)
{
#if DEBUG_ENABLE
printf("%c",ch);
#endif /*DEBUG_ENABLE*/
switch(getCharType(ch))
{
/*Arithmetic Expression or possibly comment starts here*/
case isOpeningBrace :
if((chtmp=mygetch(infile))!=EOF)
{
if(getCharType(chtmp)== isStar)
{
CmmntScanning = True;
#if DEBUG_ENABLE
printf("\nCmmnt Scanning = True\n");
#endif /*DEBUG_ENABLE*/
}
else if (CmmntScanning == False)
{
ArthExpScanning += 1;
#if DEBUG_ENABLE
printf("\nArthExpScanning = %d\n",ArthExpScanning);
#endif /*DEBUG_ENABLE*/
if(ungetch(chtmp) == INSUFFICIENT_BUFFER)
{
return (0);
}
}
}
break;
/*Arithmetic Expression possibly closes here */
case isClosingBrace :
if(CmmntScanning == False)
{
ArthExpScanning -= 1;
#if DEBUG_ENABLE
printf("\nArthExpScanning = %d\n",ArthExpScanning);
#endif /*DEBUG_ENABLE*/
}
#if DEBUG_ENABLE
if(ArthExpScanning < 0)
{
printf("\nerror here!!\n");
}
#endif /*DEBUG_ENABLE*/
break;
case isStar :
if((chtmp=mygetch(infile))!=EOF)
{
if((getCharType(chtmp)== isClosingBrace) && (CmmntScanning == True))
{
CmmntScanning = False;
#if DEBUG_ENABLE
printf("\nCmmnt Scanning = False\n");
#endif /*DEBUG_ENABLE*/
}
else
{
if(ungetch(chtmp) == INSUFFICIENT_BUFFER)
{
return (0);
}
}
}
break;
case isSpace :
if((CmmntScanning == False) && (ArthExpScanning != 0))
{
/* Space not allowed while scanning arith exp */
#if DEBUG_ENABLE
printf("NO \n");
#endif /*DEBUG_ENABLE*/
return 0;
}
break;
case isAlphabet :
case isOperator :
case isNumber :
case isNewline :
default:
break;
}
}
if((ArthExpScanning == 0) && (CmmntScanning == False))
{
/* if there are no open braces and comments left after parsing the entire
file return success*/
return 1;
}
else
{
return 0;
}
}
int main(int argc,char *argv[])
{
FILE *infile;
if(argc != 2)
{
printf("Correct usage is : D++ExpParser inputfilename\n");
return (-1);
}
if((infile = fopen(argv[1],"r")) == NULL )
{
printf("Not able to open file : %f\n",argv[1]);
return (-2);
}
if(parseInputFile(infile))
{
printf("YES\n");
}
else
{
printf("NO\n");
}
fclose(infile);
}