Balanced Parenthesis in C
In this topic, we will learn how to check the balanced parenthesis in C. First, we will see what are the parenthesis. The parenthesis is represented by the brackets shown below:
These parentheses are used to represent the mathematical representation. The balanced parenthesis means that when the opening parenthesis is equal to the closing parenthesis, then it is a balanced parenthesis.
Let’s understand through examples.
Example 1: ( 2+5 ) * 4
In the above expression, there is one opening and one closing parenthesis means that both opening and closing brackets are equal; therefore, the above expression is a balanced parenthesis.
Example 2: 2 * ( ( 4/2 ) + 5 )
The above expression has two opening and two closing brackets which means that the above expression is a balanced parenthesis.
Example 3: 2 * ( ( 4/2 ) + 5
The above expression has two opening brackets and one closing bracket, which means that both opening and closing brackets are not equal; therefore, the above expression is unbalanced.
Algorithm to check balanced parenthesis
Now, we will check the balanced parenthesis by using a variable. The variable is used to determine the balance factor. Let’s consider the variable ‘x’. The algorithm to check the balanced parenthesis is given below:
Step 1: Set x equal to 0.
Step 2: Scan the expression from left to right.
For each opening bracket “(“, increment x by 1.
For each closing bracket “)”, decrement x by 1.
This step will continue scanning until x<0.
Step 3: If x is equal to 0, then
“Expression is balanced.”
“Expression is unbalanced.”
Let’s understand the above algorithm through an example.
Suppose expression is 2 * ( 6 + 5 )
Solution: First, the x variable is initialized by 0. The scanning starts from the variable ‘2’, when it encounters ‘(‘ then the ‘x’ variable gets incremented by 1 and when the x reaches to the last symbol of the expression, i.e., ‘)’ then the ‘x’ variable gets decremented by 1 and it’s final value becomes 0. We have learnt in the above algorithm that if x is equal to 0 means the expression is balanced; therefore, the above expression is a balanced expression.
Implementation in C