Algorithm or program to check for balanced parentheses in an expression using stack data structure.
For example:
[(+) * (-)] // true
{[()]} // true
{(}) // false
{*) //false
The idea to solve the problem is:
- opening and closing parentheses should have the same number
- last unclosed should be closed first!
const closing = [')', ']', '}'];
const opening = ['(', '[', '{'];
const matching = {
: ['(', ')'],
: ['[', ']'],
: ['{', '}']
}; const contains = ary => target => ary.includes(target);
const isOpening = contains(opening);
const isClosing = contains(closing); function balanceParentheses (str) {
let stack = [];
const isEmpty = stack => stack.length === ;
const last = stack => stack[stack.length - ]; for (let char of str) {
// if it is open char, push to the stack
if (isOpening(char)) {
stack.push(char);
}
// if it is closing char
else if (isClosing(char)) {
// if stack is not empty
if (!isEmpty(stack)) {
// check last element should be the pair of closing element
const indx = closing.indexOf(char);
const [open, close] = matching[indx];
// if it is, then pop the last element
if (last(stack) === open) {
stack.pop();
} else {
// otherwise, return false
return false;
}
} else {
return false;
}
}
} return isEmpty(stack);
} console.log(balanceParentheses('{[()(){}]}')); // true
console.log(balanceParentheses(')(')); // false
console.log(balanceParentheses('({)}')); // false
console.log(balanceParentheses('{2*3)')); // false
console.log(balanceParentheses('[(1+2)*3-(1-9)]')); //true