/***********************************************
Copyright (c) 2013, [email protected]
***********************************************/
/*=================================================================
判斷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;
}
