An algorithm to check if an expressions (parentheses) given in a string are balanced or not.
Example
Input: '[{}]' '[{}{}{}}]' Output: true false
We will use Stack to solve the balanced parentheses problem.
Implementation
- We have to create a Stack of characters.
- We are then going to traverse through the given string and check if the characters matches to any one of these β{β, β(β, β[β then push it into the Stack.
- If the characters matches to β}β, β)β, β]β then pop an item from the Stack and check if it matches to its corresponding parentheses.
- If it matches then continue and check for others, otherwise it is not balanced.
- In the end after traversing the string if there are still items in stack then also it is not balanced.
// stack function Stack(){ var items = []; var top = 0; //other methods go here //Push an item in the Stack this.push = function(element){ items[top++] = element } //top++, first performs the operation then increment's the value //Pop an item from the Stack this.pop = function(){ return items[--top]; } //--top, first decrements the value then performs the operation //Peek top item from the Stack this.peek = function(){ return items[top - 1]; } //Is Stack empty this.isEmpty = function(){ return top === 0; } //Clear the Stack this.clear = function(){ top = 0; } //Size of the Stack this.size = function(){ return top; } } //Function to check balanced parantheses let checkBalancedParentheses = (str) => { //Create a stack let stack = new Stack(); for(let i = 0; i < str.length; i++){ if(str[i] == '{' || str[i] == '(' || str[i] == '['){ stack.push(str[i]); } if(str[i] == '}' || str[i] == ')' || str[i] == ']'){ //return false if stack is empty if(stack.isEmpty()){ return false; } //Pop an item from the stack and check if it matches the corresponding parentheses let temp = stack.pop(); if(temp == '{' && str[i] != '}'){ return false; }else if(temp == '[' && str[i] != ']'){ return false; }else if(temp == '(' && str[i] != ')'){ return false; } } } //If stack is empty after traversing the string then return true if(stack.isEmpty()){ return true; }else{ return false; } }
Input: console.log(checkBalancedParentheses('[{}]')); console.log(checkBalancedParentheses('[{}{}{}{]')); console.log(checkBalancedParentheses('({[]}){}[][({})]')); Output: //How it works /* stack = new Stack(); loop each character of string first character = '[' if(character == '{' || character == '[' || character == '('){ stack.push(character) = ['['] } second character = '{' if(character == '{' || character == '[' || character == '('){ stack.push(character) = ['{','['] } third character = '}' if(character == '}' || character == ']' || character == ')'){ //Condition is false if(stack.isEmpty()){ return false; } var temp = stack.pop(); temp = '{' //Condition is false if(temp == '{' && str[i] != '}'){ return false } } do the same for all the characters in the string in the end, check if the stack is empty or not return true if empty else return false; */ true false true
Time Complexity: O(n) where n is the no of characters in the string.
Space Complexity: O(n) where n is the no of characters in the string.
Time and Space complexity
- We are traversing through each character of string, Time complexity O(n).
- We are storing the opposite parentheses characters in the stack, in the worst case there can be all the opposite characters in the string, Space complexity O(n).