(Your)((Term)((Project)))
Description
You have typed the report of your term project in your personal computer. There are several one line arithmetic expressions in your report. There is no redundant parentheses in the expressions (omitting a pair of redundant matching parentheses does not change the value of the expression). In your absence, your little brother inserts some redundant matching parentheses in the expressions of your report. Assume that the expressions remain syntactically correct and evaluate to their original value (the value before inserting redundant parentheses). To restore your report to its original form, you are to write a program to omit all redundant parentheses.
To make life easier, consider the following simplifying assumptions:
- The input file contains a number of expressions, each in one separate line.
- Variables in the expressions are only single uppercase letters.
- Operators in the expressions are only binary ‘+’ and binary ‘-‘.
Note that the only transformation allowed is omission of redundant parentheses, and no algebraic simplification is allowed.
Input
The input consists of several test cases. The first line of the file contains a single number M, which is the number of test cases (1 <= M <= 10). Each of the following M lines, is exactly one correct expression. There may be arbitrarily space characters in each line. The length of each line (including spaces) is at most 255 characters.
Output
The output for each test case is the same expression without redundant parentheses. Notice that the order of operands in an input expression and its corresponding output should be the same. Each output expression must be on a separate line. Space characters should be omitted in the output expressions.
Sample Input
3 (A-B + C) - (A+(B - C)) - (C-(D- E) ) ((A)-( (B))) A-(B+C)
Sample Output
A-B+C-(A+B-C)-(C-(D-E)) A-B A-(B+C)
我的代码
以下三种情况的括号可以被消去：最开头的一对、不包含着加减运算符的一对、前面的运算符号不是减号的一对。需要先利用栈来将所有的括号先进行配对，然后再处理消去问题。
#include<stdio.h>
#include<stack>
#include<string.h>
using namespace std;
stack<int> s;
int main()
{
int m;
scanf("%d",&m);
getchar();
while(m--)
{
// char temp;
// char express[300];
// int pre[300]={0};
// int flag[300];
// int now=0;
// while(scanf("%c",&temp)&&temp!='\n')
// {
// if (temp!=' ')
// express[now++]=temp;
// }
char temp[300];
char express[300];
int pre[300]={0};
int flag[300];
int now=0;
gets(temp);
int len=strlen(temp);
for (int i = 0; i < len; i++)
{
if (temp[i] != ' ')
{
express[now++] = temp[i];
}
}
express[now]='#include<stdio.h>
#include<stack>
#include<string.h>
using namespace std;
stack<int> s;
int main()
{
int m;
scanf("%d",&m);
getchar();
while(m--)
{
// char temp;
// char express[300];
// int pre[300]={0};
// int flag[300];
// int now=0;
// while(scanf("%c",&temp)&&temp!='\n')
// {
// if (temp!=' ')
// express[now++]=temp;
// }
char temp[300];
char express[300];
int pre[300]={0};
int flag[300];
int now=0;
gets(temp);
int len=strlen(temp);
for (int i = 0; i < len; i++)
{
if (temp[i] != ' ')
{
express[now++] = temp[i];
}
}
express[now]='\0';
while (!s.empty()) s.pop();
for (int i=0;i<now;i++)
{
if (express[i]=='(') s.push(i);
if (express[i]==')')
{
pre[i]=s.top();
s.pop();
}
}
for (int i=0;i<now;i++)
{
if (express[i]==')')
{
int flag=0;
for (int j=i;j>=pre[i];j--)
{
if (express[j]=='+'||express[j]=='-')
{
flag=1;
break;
}
}
if (pre[i]==0) express[pre[i]]=express[i]=' ';
else if (express[pre[i]-1]!='-') express[pre[i]]=express[i]=' ';
else if (!flag) express[pre[i]]=express[i]=' ';
}
}
for (int i=0;i<now;i++) if (express[i]!=' ') printf("%c",express[i]);
printf("\n");
}
return 0;
';
while (!s.empty()) s.pop();
for (int i=0;i<now;i++)
{
if (express[i]=='(') s.push(i);
if (express[i]==')')
{
pre[i]=s.top();
s.pop();
}
}
for (int i=0;i<now;i++)
{
if (express[i]==')')
{
int flag=0;
for (int j=i;j>=pre[i];j--)
{
if (express[j]=='+'||express[j]=='-')
{
flag=1;
break;
}
}
if (pre[i]==0) express[pre[i]]=express[i]=' ';
else if (express[pre[i]-1]!='-') express[pre[i]]=express[i]=' ';
else if (!flag) express[pre[i]]=express[i]=' ';
}
}
for (int i=0;i<now;i++) if (express[i]!=' ') printf("%c",express[i]);
printf("\n");
}
return 0;反思
正如我所注释的部分所见，用注释部分的方式读取一整行字符是不正确的（起码在poj上）：
while(scanf("%c",&temp)&&temp!='\n')
{
if (temp!=' ')
express[now++]=temp;
}我re了一中午，一直以为是栈用的有问题。直到现在也没有搞明白为什么这种输入方式有问题。