華為2014機考題_判斷if括號是否匹配_堆棧

/***********************************************
 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;
}