Question

ACM OJ扩号匹配问题 总是wrong answer 找不出问题

Description

在某个字符串（长度不超过100）中有左括号、右括号和大小写字母；规定（与常见的算数式子一样）任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序，找到无法匹配的左括号和右括号，输出原来字符串，并在下一行标出不能匹配的括号。不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注.

Input

输入包括多组数据，每组数据一行，包含一个字符串，只包含左右括号和大小写字母，字符串长度不超过100
注意：cin.getline(str,100)最多只能输入99个字符！

Output

对每组输出数据，输出两行，第一行包含原始输入字符，第二行由"$","?"和空格组成，"$"和"?"表示与之对应的左括号和右括号不能匹配。

Sample Input

((ABCD(x)
)(rttyy())sss)(

Sample Output

((ABCD(x)
$$
)(rttyy())sss)(
? ?$

下面是我的代码
#include <stdio.h>
#include <malloc.h>
#include <string.h>
typedef char SElemType;

#define STACK_INIT_SIZE 110

typedef struct SqStack
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;

int InitStack(SqStack *S)
{
(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if( !(*S).base )
exit(0);
(*S).top = (*S).base;
(*S).stacksize = STACK_INIT_SIZE;
return 1;
}

int StackEmpty(SqStack S)
{
if(S.top == S.base)
return 1;
else
return 0;
}

int Push(SqStack *S, SElemType e)
{
*(((*S).top)++)=e;
return 1;
}

int Pop(SqStack *S)
{
if((*S).top == (*S).base)
return 0;
(*S).top--;
return 1;
}

int main()
{
SqStack s;
SElemType ch[110], *p;
char temp[110];
int tempnum[110];
int count, figure;
int i;
while(fgets(ch, 101, stdin))
{
count = 0;
figure = 0;
InitStack( &s );
p = ch;
while(*p)// 没到串尾
{
switch(*p)
{
case '(':
Push(&s,*p++);
tempnum[figure++]=count;
temp[count++]='$';
break;
case ')':
if(!StackEmpty(s))
{
Pop(&s);
temp[count++]=' ';
temp[tempnum[figure-1]]=' ';
figure--;
p++;
break;
}
else
{
temp[count++]='?';
p++;
break;
}
default:
p++;
temp[count++] = ' ';
}
temp[count]='\0';
}
p = ch;
for(i = 0; i < count - 1; i++)
printf("%c", *p++);
printf("\n");
p = temp;
for(i = 0; i < count - 1; i++)
printf("%c", *p++);
printf("\n");
}
return 0;
}
哪个好心的大牛帮小弟看看哪里要改进，非常感谢

Answer 1

1.为什么把简单问题复杂化呢？你觉得你的stack在这里有什么用，stack部分就是一堆废代码。要判断堆栈是不是空其实就是判断figure是不是为0.
2.没必要用指针，指针很容易出错，这就是为什么java语言都把指针给舍弃了的原因。
3.我个人虽然说的比较不客气，但编程确实是这样，力求简单清晰明了，并且要想清楚每一部分代码的作用，否则这些代码就是冗余的，程序就不好。希望对你有帮助

核心程序，不一定正确，是按你的思路写的简洁版：
int main(){
char ch[110],temp[110];
int i,figure;
while(gets(ch)){
figure = 0;
for(i=0;ch[i] != '\0';i ++)
{
temp[i]=' ';
switch(ch[i]){
case '(':tempnum[figure ++]=i;temp[i]='$';break;
case ')':
if(figure){figure--;temp[tempnum[figure]]=' ';}
else temp[i] = '?';break;
}
}
temp[i]='\0';
printf("%s\n%s\n",ch,temp);
}
return 0;
}

追问

哈，豁然开朗，非常感谢！= =其实挺简单的一道题目
因为小弟ACM刚入门也是初学的数据结构没代码能力= =然后就直接把栈的代码拿出来直接改= =没有深入思考按书上说的照搬照套。。。希望以后多思考多练习吧
总之，感谢了！