CODEWITHSUNDEEP
c++
user15329767
user15329767

Reputation:

C++: Checking if the order of parentheses and brackets from a string is correct using stacks

I have to create a function using pop() and push() to check if the order of the parentheses and brackets is correct, for exemple "( ( [ [ ] ] ) )" is correct, but "( ( ( [ ] ] ) )" is not.

My idea was to make a loop and for each iteration get a char from the string and check if its an opening (bracket or parentheses) then push it, if it's a closing then check if the top() from stack is an opening of the same kind, if it is not then return false, if it is then pop() and continue the loop, until the string ends.

The problem is that I don't know why my code doesn't work.

Thanks in advance!

#include <iostream>
#include <stack>  
using namespace std;

bool checkExpress(string str){
    int i;
    stack <char> st;
    
    if(str.length() % 2 != 0) return false;
    
    for(i=0; i < str.length(); i++){

        if(str[i] == '(' || str[i] == '[') st.push(str[i]);
        
        else if(str[i] == ')' || str[i] == ']'){

            if(str[i] == ']' && st.top() != '[') return false;

            else if(str[i] == ')' && st.top() != '(') return false;
        }

        st.pop();   
    }

    return true;
}


int main(){
    string a = "(([[]]))";
    
    if(checkExpress(a)) cout << "The expression is well constructed.";
    else cout << "The expression is not well constructed.";

    return 0;
}

Upvotes: 1

Views: 1356

Answers (2)

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275350

Change

    }

    st.pop();

to

        st.pop();
    }

or more completely:

for(char ch : str){
  if (ch == '(' || ch == '[') {
    st.push(ch);
    continue;
  }
  if (st.empty())
    return false;
  char top = st.top();
  st.pop();
  
  if (top == '(' && ch==')')
    continue; // we good
  if (top == '[' && ch==']')
    continue; // we good

  return false; // invalid character, or bad match
}

this is an early exit style; we do as much state work as early as possible, then exit out (either continue the loop, or return) when we know we have the right answer for this cycle.

We start with the open bracket case; we push the state and loop, because we are done.

Then, if the string is valid, it must have a close braket. So we do the state transition first, covering the "paperwork". Then we validate that we are good; if we are, all we have to do is continue, as all of the state paperwork is completed.

As a side bonus, the '(' and ')' visually line up. :)

Upvotes: 1

Marek R
Marek R

Reputation: 37647

There are two problems in your code:

  1. you are doing pop for opening and closing brackets and plan was to do it only for closing brackets
  2. you didn't take into account possibility that stack can be empty during iteration. For example: ()) will lead to undefined behavior even if fix from other answer will be applied.

If should go this way:

bool checkExpress(string str){
    int i;
    stack <char> st;
    
    if(str.length() % 2 != 0) return false;
    
    for(auto ch : str){

        if (ch == '(' || ch == '[') {
            st.push(ch);
        } else if(ch == ')') {
            if(st.empty() || st.top() != '(') return false;
            st.pop();
        } else if(ch == ']') {
            if(st.empty() || st.top() != '[') return false;
            st.pop();
        } 
    }

    return true;
}

Upvotes: 1

Related Questions