The valid parentheses problem

The valid parentheses problem involves checking that:

  1. all the parentheses are matched, i.e., every opening parenthesis has a corresponding closing parenthesis.
  2. the matched parentheses are in the correct order​, i.e., an opening parenthesis should come before the closing parenthesis.
svg viewer

Algorithm

  1. Declare an empty stack.
  2. Push an opening parenthesis on top of the stack.
  3. In case of a closing bracket, check if the stack is empty.
  4. If not, pop in a closing parenthesis if the top of the stack contains the corresponding opening parenthesis.
  5. If the parentheses are valid,​ then the stack will be empty once the input string finishes.

Implementation

Copyright ©2024 Educative, Inc. All rights reserved