C++ USES the stack to determine the implementation of the parenthesis string matching problem

  • 2020-04-02 02:39:25
  • OfStack

This example is mainly implemented: input a bracket string, check in sequence, if the left bracket is pushed, if the right bracket is pushed a character to determine whether it corresponds to, in the end also need to determine whether the stack is empty, if not empty will not match.

First, review the stack basics:

1. Define the stack structure and initialize a new stack:


struct stack
{
  char strstack[stacksize];
  int top;
};

void InitStack(stack &s)
{
  s.top=-1;
}

2. Push out and push operation:


char Push(stack &s,char a)
{
  if(s.top==stacksize-1)
  {
    return 0;
  }
  s.top++;
  s.strstack[s.top]=a;
  return a;
}

char Pop(stack &s)
{
  if(s.top==-1)
  {
    return 0;
  }
  char a=s.strstack[s.top];
  s.top--;
  return a;
}

3. Determine whether the stack is empty:


int Empty(stack &s,int re)
{
  if(s.top==-1)
  {
    return 1;
  }
  else
  {
    return 0;
  }
}

These are the basic operations of the stack, defining a stack and initializing a new stack, the operations of the stack and the operations of the push, and determining whether the stack is empty. Next, a function is written that checks each character of the string, the left parenthesis is pushed, the right parenthesis is pushed to see if it matches, and finally the null is determined to see if it matches.

The main function code is as follows:


int Check(char *str)
{
  stack s;
  InitStack(s);
  int strn=strlen(str);
  for(int i=0;i<strn;i++)
  {
    char a=str[i];
    switch (a)
    {
    case '(':
    case '[':
    case '{':
      Push(s,a);
      break;
    case ')':
      if(Pop(s)!='(')
      {
        return 0;
      }
      break;
    case ']':
      if(Pop(s)!='[')
      {
        return 0;
      }
      break;
    case '}':
      if(Pop(s)!='{')
      {
        return 0;
      }
      break;
    }
  }
  int re=0;
  re=Empty(s,re);
  if(re==1)
  {
    return 1;
  }
  else
  {
    return 0;
  }
}

Since then, the bracket string matching problem has been resolved, and the full compiled and run code is posted below.

The complete example code is as follows:


#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define stacksize 100
struct stack
{
  char strstack[stacksize];
  int top;
};
void InitStack(stack &s)
{
  s.top=-1;
}
char Push(stack &s,char a)
{
  if(s.top==stacksize-1)
  {
    return 0;
  }
  s.top++;
  s.strstack[s.top]=a;
  return a;
}
char Pop(stack &s)
{
  if(s.top==-1)
  {
    return 0;
  }
  char a=s.strstack[s.top];
  s.top--;
  return a;
}
int Empty(stack &s,int re)
{
  if(s.top==-1)
  {
    return 1;
  }
  else
  {
    return 0;
  }
}
int Check(char *str)
{
  stack s;
  InitStack(s);
  int strn=strlen(str);
  for(int i=0;i<strn;i++)
  {
    char a=str[i];
    switch (a)
    {
    case '(':
    case '[':
    case '{':
      Push(s,a);
      break;
    case ')':
      if(Pop(s)!='(')
      {
        return 0;
      }
      break;
    case ']':
      if(Pop(s)!='[')
      {
        return 0;
      }
      break;
    case '}':
      if(Pop(s)!='{')
      {
        return 0;
      }
      break;
    }
  }
  int re=0;
  re=Empty(s,re);
  if(re==1)
  {
    return 1;
  }
  else
  {
    return 0;
  }
}
void main()
{
  char str[100];
  cout<<" Please enter a length less than 100 The string :"<<endl;
  cin>>str;
  int re=Check(str);
  if(re==1)
  {
    cout<<" The string parenthesis you entered exactly matches! "<<endl;
  }
  else if(re==0)
  {
    cout<<" The string parenthesis you entered does not match! "<<endl;
  }
}

I hope the examples described in this paper are helpful to the learning of C++ algorithm design.


Related articles: