华为2014机考题_判断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;
}

华为2014校园招聘经历_底层软件研发_机考

华为2014机考题目_判断if括号匹配是否合法_堆栈_简单的方法- -

相关内容