判断if括号是否匹配

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

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/bd213a4e058f6c82669926069082c942.html