/***********************************************
Copyright (c) 2013, binzhouweichao@163.com
***********************************************/
/*=================================================================
判断if语句括号是否合法
编程的时候，if条件里面的“(”、“)”括号经常出现不匹配的情况导致编译不过，请编写程序检测输入一行if语句中的圆括号是否匹配正确。同时输出语句中出现的左括号和右括号数量，如if((a==1)&&(b==1))是正确的，而if((a==1))&&(b==1))是错误的。注意if语句的最外面至少有一对括号。提示：用堆栈来做。
输入：if((a==1)&&(b==1))
输出：RIGTH 3 3
输入：if((a==1))&&(b==1))
输出：WRONG 3 4
===================================================================*/
#include <iostream> //输入输出流操作
#include <string> //字符串操作
#define DEBUG //调试时多余的操作，最后发布时去掉此句即可
#define NULL 0 //空指针，0表示指针不指向任何对象
using namespace std; //启用标准库命名空间
//堆栈的各项定义和操作
//堆栈结点结构
typedef struct stackNode
{
char data; //数据域，其实可以去掉数据域。。
struct stackNode *nextNode; //指针域，指向下一个结点；指针方向：栈顶-->栈底
}stackNode;
//堆栈结构
typedef struct
{
stackNode *top; //只需要一个栈顶指针即可
}stack;
//初始化堆栈
void InitStack(stack *s)
{
s->top = new stackNode; //为栈顶开辟内存
s->top->nextNode = NULL; //栈顶指向空，此为空栈的判别标志
}
//判断是否空栈，空栈返回1，非空返回0
int StackEmpty(stack *s)
{
return(s->top->nextNode == NULL ? 1:0);
}
//压栈
void PushStack(stack *s, char ch)
{
stackNode *p = new stackNode; //开辟新结点
p->data = ch;
p->nextNode = s->top->nextNode; //新结点指针域为栈顶指向的对象，如果空栈，栈顶指向空，则新结点为第一个结点，也就是栈底，其指针域为空；若非空栈，栈顶指针需要下述操作
s->top->nextNode = p; //栈顶指针域指向新结点，解决了上一步非空栈的情况
}
//出栈，内部没有空栈判定，需要在调用前先判定堆栈是否为空
void PopStack(stack *s)
{
stackNode *p; //新建缓存结点
p = s->top->nextNode; //前提是堆栈非空；p缓存栈顶结点单元
// *m = p->data; //栈顶数据域存入m单元，备用
s->top->nextNode = p->nextNode; //栈顶指向原先栈顶单元的下一个结点
//若p为栈底，则栈顶指针域指向NULL，表示栈已空
free(p); //清除缓存
}
int main()
{
string str; //输入的字符串存储位置
getline(cin, str); //cin以空格作为结束标志，故采用读取第一行的方式输入
//int flag = 1; //设置字符串括号正确与否的标志，正确为1，错误为0
//先将左右括号数目查找出来
//如果左右括号不相等，直接输出“WRONG”，加上左右括号数，结束程序；
//若左右括号相等，再进行下一步的判断
int cntl, cntr; //左右括号变量，初始为0
cntl = cntr = 0; //0说明无括号，与if至少有一个外层括号冲突，可以作为错误的一种情况
int len = strlen(str.c_str()); //输入的字符串长度
for(int i=0; i<len; i++)
{
if(str[i] == '(') //字符串元素的调用方式，各元素为char类型
{
cntl++;
}
if(str[i] == ')')
{
cntr++;
}
}
if((cntl != cntr) || (cntl == 0)) //若左右括号数不一致，或左（右）括号数为0，代表错误
{
cout << "WRONG" << " " << cntl << " " << cntr;
#ifdef DEBUG
system("pause");
#endif
return 0; //程序结束，下面的判断就不必进行了
}
//若左右括号数一致，且至少有一对左右括号，进行下面的判断
stack s; //声明堆栈s
InitStack(&s); //初始化堆栈s
int popStackCnt = 0; //出栈计数器，用于判断出栈至空栈时，右括号是否已经计完，若未计完右括号就已经空栈，说明最外层至少一对括号错误
for(int i=0; i<len; i++)
{
if(str[i] == '(') //遇到左括号，压栈
{
PushStack(&s, str[i]);
}
if(str[i] == ')') //遇到右括号，出栈；
{
if(StackEmpty(&s)) //如果在空栈的情况下还要出栈，说明右括号不匹配，打印消息并结束程序
{
cout << "WRONG" << " " << cntl << " " << cntr;
#ifdef DEBUG
system("pause");
#endif
return 0;
}
else //如果非空，则正常出栈，并判断出栈后是否为空
{
PopStack(&s);
popStackCnt++; //出栈操作数，即遇到的右括号数
if(StackEmpty(&s)) //若出栈至空
{
if(popStackCnt < cntr) //若出栈至空时，出栈数小于右括号数，说明最外层至少一对括号不满足
{
cout << "WRONG" << " " << cntl << " " << cntr;
#ifdef DEBUG
system("pause");
#endif
return 0;
}
}
}
}
}
//如果上述情况均未遇到，则说明括号匹配正确，打印信息并退出
cout << "RIGHT" << " " << cntl << " " << cntr;
#ifdef DEBUG
system("pause");
#endif
return 0;
}