注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

火车的家

Put first thing first

 
 
 

日志

 
 

2014.12.15 Check for balanced parentheses in an expression  

2014-12-15 22:44:53|  分类: 技术博客 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Given an expression string exp, write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in exp. For example, the program should print true for exp = “[()]{}{[()()]()}” and false for exp = “[(])”

Algorithm:
1) Declare a character stack S.
2) Now traverse the expression string exp.
    a) If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘) then push it to stack.
    b) If the current character is a closing bracket (‘)’ or ‘}’ or ‘]’) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
3) After complete traversal, if there is some starting bracket left in stack then “not balanced”

Implementation:

#include<stdio.h>
#include<stdlib.h>
#define bool int

/* structure of a stack node */
struct sNode
{
   char data;
   struct sNode *next;
};

/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data);

/* Function to pop an item from stack*/
int pop(struct sNode** top_ref);

/* Returns 1 if character1 and character2 are matching left
   and right Parenthesis */
bool isMatchingPair(char character1, char character2)
{
   if(character1 == '(' && character2 == ')')
     return 1;
   else if(character1 == '{' && character2 == '}')
     return 1;
   else if(character1 == '[' && character2 == ']')
     return 1;
   else
     return 0;
}

/*Return 1 if expression has balanced Parenthesis */
bool areParenthesisBalanced(char exp[])
{
   int i = 0;

   /* Declare an empty character stack */
   struct sNode *stack = NULL;

   /* Traverse the given expression to check matching parenthesis */
   while(exp[i])
   {
      /*If the exp[i] is a starting parenthesis then push it*/
      if(exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
        push(&stack, exp[i]);

      /* If exp[i] is a ending parenthesis then pop from stack and 
          check if the popped parenthesis is a matching pair*/
      if(exp[i] == '}' || exp[i] == ')' || exp[i] == ']')
      {
            
          /*If we see an ending parenthesis without a pair then return false*/
         if(stack == NULL)
           return 0; 

         /* Pop the top element from stack, if it is not a pair 
            parenthesis of character then there is a mismatch.
            This happens for expressions like {(}) */
         else if ( !isMatchingPair(pop(&stack), exp[i]) )
           return 0;
      }
      i++;
   }
   
   /* If there is something left in expression then there is a starting
      parenthesis without a closing parenthesis */
   if(stack == NULL)
     return 1; /*balanced*/
   else
     return 0;  /*not balanced*/

/* UTILITY FUNCTIONS */
/*driver program to test above functions*/
int main()
{
  char exp[100] = "{()}[]";
  if(areParenthesisBalanced(exp))
    printf("\n Balanced ");
  else
    printf("\n Not Balanced ");  \
  getchar();
}    

/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data)
{
  /* allocate node */
  struct sNode* new_node =
            (struct sNode*) malloc(sizeof(struct sNode));

  if(new_node == NULL)
  {
     printf("Stack overflow \n");
     getchar();
     exit(0);
  }           

  /* put in the data  */
  new_node->data  = new_data;

  /* link the old list off the new node */
  new_node->next = (*top_ref);  

  /* move the head to point to the new node */
  (*top_ref)    = new_node;
}

/* Function to pop an item from stack*/
int pop(struct sNode** top_ref)
{
  char res;
  struct sNode *top;

  /*If stack is empty then error */
  if(*top_ref == NULL)
  {
     printf("Stack overflow \n");
     getchar();
     exit(0);
  }
  else
  {
     top = *top_ref;
     res = top->data;
     *top_ref = top->next;
     free(top);
     return res;
  }
}

Time Complexity: O(n)
Auxiliary Space: O(n) for stack.

Please write comments if you find any bug in above codes/algorithms, or find other ways to solve the same problem

The following is my private implementation:
#include <stdlib.h>
#include <stdio.h>

/***************************
  Stack Implementation
 ****************************/

typedef char stack_base_type;

struct link_node {
    stack_base_type value;
    struct link_node * next;
} ;

struct link_node * g_stack = NULL;

void stack_push( stack_base_type para )
{
    struct link_node * p_node = (struct link_node *) malloc( sizeof (struct link_node) );

    p_node->value = para;
    p_node->next = g_stack;

    g_stack = p_node;
}

stack_base_type stack_pop()
{
    stack_base_type value;
    struct link_node * p_tmp = NULL;

    if ( g_stack == NULL ) {
        printf( "stack overflow\n" );
        exit( 0 );
    }

    p_tmp = g_stack;
    value = g_stack->value;
    g_stack = g_stack->next;

    free( p_tmp );
    
    return value;
}

int stack_empty()
{
    return ( g_stack? 0: 1 );
}

stack_base_type stack_top()
{
    return g_stack->value;
}

int is_balanced( char left, char right )
{
    if ( left == '[' && right == ']' ) {
        return 1;
    } else if ( left == '(' && right == ')' ) {
        return 1;
    } 
    
    return 0;
}

int checkstring( char * p_string )
{
    int i = 0;

    printf("check string = %s\n", p_string);

    while( p_string[i] ) {
        if ( p_string[i] == '[' || p_string[i] == '(' ) {
            stack_push( p_string[i] );
        } else if ( p_string[i] == ']' || p_string[i] == ')' ) {
            if ( stack_empty() || is_balanced (stack_pop(), p_string[i] ) == 0 ) {
                return 0;
            }
        }

        ++i;
    }

    if ( stack_empty() == 0 ) {
        return 0;
    }

    return 1;
}

int main ( int argc, char * argv[] )
{
    char * p_test = "[]()";
/*  char * p_test = ")[]()";
    char * p_test = "[()";
    char * p_test = "([)]";*/

    if ( checkstring( p_test ) ) {
        printf("Balanced\n");
    } else {
        printf("Not balanced\n");
    }

    return 0;
}
  评论这张
 
阅读(404)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017