Skip to content

Instantly share code, notes, and snippets.

@mycodeschool
Created October 29, 2013 00:49
Show Gist options
  • Save mycodeschool/7207410 to your computer and use it in GitHub Desktop.
Save mycodeschool/7207410 to your computer and use it in GitHub Desktop.
C++ Program to check for balanced parentheses in an expression using stack.
/*
C++ Program to check for balanced parentheses in an expression using stack.
Given an expression as string comprising of opening and closing characters
of parentheses - (), curly braces - {} and square brackets - [], we need to
check whether symbols are balanced or not.
*/
#include<iostream>
#include<stack>
#include<string>
using namespace std;
// Function to check whether two characters are opening
// and closing of same type.
bool ArePair(char opening,char closing)
{
if(opening == '(' && closing == ')') return true;
else if(opening == '{' && closing == '}') return true;
else if(opening == '[' && closing == ']') return true;
return false;
}
bool AreParanthesesBalanced(string exp)
{
stack<char> S;
for(int i =0;i<exp.length();i++)
{
if(exp[i] == '(' || exp[i] == '{' || exp[i] == '[')
S.push(exp[i]);
else if(exp[i] == ')' || exp[i] == '}' || exp[i] == ']')
{
if(S.empty() || !ArePair(S.top(),exp[i]))
return false;
else
S.pop();
}
}
return S.empty() ? true:false;
}
int main()
{
/*Code to test the function AreParanthesesBalanced*/
string expression;
cout<<"Enter an expression: "; // input expression from STDIN/Console
cin>>expression;
if(AreParanthesesBalanced(expression))
cout<<"Balanced\n";
else
cout<<"Not Balanced\n";
}
@asad2200
Copy link

asad2200 commented Apr 21, 2020

Here the java code ,if someone wants

//------------------------------------

import java.util.Scanner;
import java.util.Stack;

public class CheckParathese {

static boolean checkPair(char opening,char closing){
    if(opening == '(' && closing == ')') return true;
    else if(opening == '{' && closing == '}') return true;
    else if(opening == '[' && closing == ']') return true;
    return false;
}

static boolean isBalanced(String s) {
    char arr[] = s.toCharArray();
    Stack<Character> st = new Stack<Character>();
    for(int i=0;i<s.length();i++){
        if(arr[i] == '(' || arr[i] == '{' || arr[i] == '[')
            st.push(arr[i]);
        else if(arr[i] == ')' || arr[i] == '}' || arr[i] == ']'){
            if(st.empty() || !checkPair(st.peek(),arr[i])){
                return false;
            }else
                st.pop();
        }
    }
    return st.empty()?true:false ;
}

public static void main(String[] args) throws Exception {
    String s;
    Scanner sc = new Scanner(System.in);
    s=sc.nextLine();
    sc.close();
    if(isBalanced(s))
        System.out.print("Paranthases are balanced");
    else
        System.out.print("Paranthases are not balanced");   
}

}
//-------------------------------------

@hitsa70
Copy link

hitsa70 commented Apr 29, 2020

import java.util.*;
public class Solution {

public static boolean matchingPeer(char open , char close){
if ( open == '(' && close == ')'){
return true;
}
if ( open == '[' && close == ']'){
return true;
}
if ( open == '{' && close == '}'){
return true;
}
// you can add more open and close rule

else{
return false;
}

}

public static boolean checkBalanced(String equation) 
{
	// Write your code here
	char[] c = equation.toCharArray();
Stack <Character> myStack= new Stack <Character> ();

for (int i = 0; i < c.length; i++)
{
	if(c[i]=='(' || c[i] == '[' || c[i] == '{'){
		myStack.push(c[i]);
        continue;
	}
	else if (c[i]== ')' || c[i]==']' || c[i] == '}'){
        	if(myStack.isEmpty())
                return false;
			if(matchingPeer(myStack.peek(),c[i]) == true){
				myStack.pop();
			
			} else {
				return false;
			}
	}
}
	if(myStack.isEmpty()){
		return true;
	}	
	else {
		return false;
	}
}

}

@FredLeg
Copy link

FredLeg commented May 19, 2020

JAVASCRIPT

function isParanthesesBalanced( expression ){
  let symbols = {
      'opening': ['(','[','{','«'],
      'closing': [')',']','}','»'],
      'isOpening': function( car ){
        return this.opening.indexOf(car)>=0
      },
      'isClosing': function( car ){
        return this.closing.indexOf(car)>=0
      },
      'isPair': function( opening, closing ){
        let i = this.opening.indexOf(opening)
        if( !(i>=0) ) return false
        return i == this.closing.indexOf(closing)
      }
  }
  let stack = {
    's':       [],
    'push':    function( car ){ this.s.push(car) },
    'pop':     function( car ){ this.s.pop(car) },
    'top':     function(){ return this.s[this.s.length-1] },
    'isEmpty': function(){ return this.s.length==0 }
  }
  for ( let car of expression ) {
    if( symbols.isOpening(car) )
      stack.push(car)
    else if( symbols.isClosing(car) ){
      if( stack.isEmpty() || !symbols.isPair( stack.top(), car ) )
        return false
      else
        stack.pop()
    }
  }
  return stack.isEmpty()
}

let expressions = [
  "[(a+b)*(c+d)]",
  "[()(])",
  "Elle dit « ouh là là » tout le temps.",
  "none",
  ""
]
for( exp of expressions ){
  console.log( exp +" • "+ isParanthesesBalanced(exp) )
}
[(a+b)*(c+d)] • true
[()(]) • false
Elle dit « ouh là là » tout le temps. • true
none • true
 • true

@siddharthmagadum16
Copy link

siddharthmagadum16 commented Jun 9, 2020

Here's my code. I implemented using stack . The stack is implemented using object oriented implementation using arrays.
`// Stack - ||Object oriented implementation|| using arrays
#include
using namespace std;
#define MAX_SIZE 4

class Stack
{
private:
int A[MAX_SIZE]; // array to store the stack
int top; // variable to mark the top index of stack.
public:
// constructor
Stack()
{
top = -1; // for empty array, set top = -1
}

// Push operation to insert an element on top of stack. 
void Push(int x) 
{
  if(top == MAX_SIZE -1) { // overflow case. 
		printf("Error: stack overflow\n");
		return;
	}
	A[++top] = x;
}

// Pop operation to remove an element from top of stack.
void Pop() 
{
	if(top == -1) { // If stack is empty, pop should throw error. 
		printf("Error: No element to pop\n");
		return;
	}
	top--;
}

// Top operation to return element at top of stack. 
int Top() 
{
	return A[top];
}

// This function will return 1 (true) if stack is empty, 0 (false) otherwise
int IsEmpty()
{
	if(top == -1) return 1;
	return 0;
}

// ONLY FOR TESTING - NOT A VALID OPERATION WITH STACK 
// This function is just to test the implementation of stack. 
// This will print all the elements in the stack at any stage. 
void Print() {
	int i;
	printf("Stack: ");
	for(i = 0;i<=top;i++)
		printf("%d ",A[i]);
	printf("\n");
}

};

int solve(){
Stack S;
char ch=getchar();
while(ch!='\n'){
if(ch=='{' || ch=='(' || ch=='['){
S.Push(ch);
}
else if(ch=='}' || ch==')' || ch==']'){
if(S.IsEmpty() || (S.Top()!='{' && ch=='}') || S.Top()!='(' && ch==')' || S.Top()!='[' && ch==']');
else S.Pop();
}
ch=getchar();
}
S.IsEmpty()?printf("Balanced\n"):printf("Not Balanced\n");
return 0;
}

int main()
{
printf("Enter string of braces:\n");
solve();
return 0;
}`

@diegoba90
Copy link

I'm having a hard time with this. How can i make it so that instead of having the user input the string of characters it instead reads it from a file that has lines of different expressions.

@rohitverma1999hack
Copy link

return S.empty() ? true:false; is kind of redundant (if true return true else return false).
It's not redundant
what if the input is "(".

@umamahesh33
Copy link

it will fail for the test case when we include the space in the user input because the taking of string input will not execute after a blank space

@shoaibrain
Copy link

shoaibrain commented Oct 9, 2020

`def balancedBrackets(string):
#remove all invalid characters. This is optional by the way.If your string only contains [{()}]. You don't have to change input string in any
way
string = [x for x in string if x in '[{()}]]']

stack = []

for char in string:
	if char in '([{':
		stack.append(char)
	else:
		if len(stack) == 0  or not arePair(stack[-1], char):
			return False
		else:
			stack.pop()
if len(stack) == 0:return True
return `False`

def arePair(opening,closing):
if opening == '(' and closing == ')':return True
elif opening == '[' and closing == ']': return True
elif opening == '{' and closing == '}':return True
return False
`

@BaseMax
Copy link

BaseMax commented Apr 11, 2021

@ibrahimBanat
Copy link

Solution Using JavaScript: you can also check the whiteboard and test from here:

class MultiBracketValidation {
  constructor() {
    this.stack = new Stack();
    this.opening = ["{", "(", "[", "<"];
    this.closing = ["}", ")", "]", ">"];
  }
  checkForValidation(input) {
    for (const char of input) {
      if (this.isOpening(char)) {
        this.stack.push(char);
      } else if (this.isClosing(char)) {
        if (
          this.stack.isEmpty() ||
          !this.isPair(this.stack.peek().value, char)
        ) {
          return false;
        } else {
          this.stack.pop();
        }
      }
    }
    return this.stack.isEmpty();
  }
  isOpening(char) {
    return this.opening.indexOf(char) >= 0;
  }
  isClosing(char) {
    return this.closing.indexOf(char) >= 0;
  }
  isPair(opening, closing) {
    return this.closing.indexOf(closing) === this.opening.indexOf(opening);
  }
}

@HarshKakran
Copy link

Hey, I am a beginner in programming, and tried to implement the pseudo code shared in the video using C++, can you guys share the reviews about the coding style.

bool checkBalancedParenthesis(string exp){
    stack<char> s;
    int n = exp.length();
    for(int i=0; i<n; i++){
        if (exp[i] == '{' || exp[i] == '(' || exp[i] == '['){
            s.push(exp[i]);
        }
        else if(exp[i] == '}' || exp[i] == ')' || exp[i] == ']'){
            if (s.empty())
            return false;
            switch (s.top())
            {
            case '(':
                if (exp[i] == ')')
                    {s.pop();
                    break;}
                else{
                    return false;
                }
            case '{':
                if (exp[i] == '}')
                    {s.pop();
                    break;}
                else{
                    return false;
                }
            case '[':
                if (exp[i] == ']')
                    {s.pop();
                    break;}
                else{
                    return false;
                }
            }
        }    
    }
    return s.empty()?true:false;
}

@AshAman999
Copy link

Hey, I am a beginner in programming, and tried to implement the pseudo code shared in the video using C++, can you guys share the reviews about the coding style.

bool checkBalancedParenthesis(string exp){
    stack<char> s;
    int n = exp.length();
    for(int i=0; i<n; i++){
        if (exp[i] == '{' || exp[i] == '(' || exp[i] == '['){
            s.push(exp[i]);
        }
        else if(exp[i] == '}' || exp[i] == ')' || exp[i] == ']'){
            if (s.empty())
            return false;
            switch (s.top())
            {
            case '(':
                if (exp[i] == ')')
                    {s.pop();
                    break;}
                else{
                    return false;
                }
            case '{':
                if (exp[i] == '}')
                    {s.pop();
                    break;}
                else{
                    return false;
                }
            case '[':
                if (exp[i] == ']')
                    {s.pop();
                    break;}
                else{
                    return false;
                }
            }
        }    
    }
    return s.empty()?true:false;
}

If you are waiting for the mentors to reply then they ain't goint to reply and apart from that yeah coding style looks good

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment