C++ Program to Check for Balanced Parentheses in an Expression

1. Introduction

Balanced parentheses in an expression are vital to ensure its correctness, especially in programming or mathematical contexts. An expression is said to have balanced parentheses if every opening bracket has a corresponding closing bracket and vice versa. 

In this tutorial, we'll use a stack data structure to verify the balance of parentheses in a given string.

2. Program Overview

The program will:

1. Implement a stack to assist in checking for balanced parentheses.

2. Create a function that:

- Processes each character of the expression.

- Uses the stack to match opening and closing brackets.

3. Display whether the expression has balanced parentheses.

3. Code Program

#include<iostream>
#include<stack>
using namespace std;

// Function to check if a character is an opening bracket
bool isOpening(char c) {
    return c == '(' || c == '{' || c == '[';
}

// Function to check if two characters are a matching pair
bool isMatchingPair(char opening, char closing) {
    return (opening == '(' && closing == ')') ||
           (opening == '{' && closing == '}') ||
           (opening == '[' && closing == ']');
}

bool areParenthesesBalanced(string expr) {
    stack<char> s;

    // Process every character in the string
    for (char& c : expr) {
        // If the character is an opening bracket, push it onto the stack
        if (isOpening(c)) {
            s.push(c);
        } else {
            // If the stack is empty, return false as this implies a missing opening bracket
            if (s.empty()) return false;

            // If the top of the stack doesn't match with the current character, return false
            if (!isMatchingPair(s.top(), c)) return false;

            s.pop();  // Remove the top bracket as it's matched
        }
    }

    // If the stack is not empty at the end, then it implies some unmatched opening brackets
    return s.empty();
}

int main() {
    string expr = "{()[{}]}";

    if (areParenthesesBalanced(expr))
        cout << "Balanced" << endl;
    else
        cout << "Not Balanced" << endl;

    return 0;
}

Output:

Balanced

4. Step By Step Explanation

1. The program utilizes a stack to ensure that the expression has balanced parentheses.

2. For every opening bracket encountered in the expression, it's pushed onto the stack.

3. For every closing bracket encountered, the program checks if it matches the corresponding opening bracket from the top of the stack. If not, the parentheses are imbalanced.

4. After processing the entire string, if there are any unmatched opening brackets left on the stack, the parentheses are deemed imbalanced.

5. The helper functions isOpening and isMatchingPair make the main function cleaner and more intuitive.

The included comments provide further insight into each step of the process.