Question

Hello, I am trying to write a C++ program that will do the following:

1. Use the STL stack container in a program that reads a string, an arithmetic expression to be exact, one character at a time, and determines if the string has balanced parenthesis – that is, for each left parenthesis there is exactly one matching right parenthesis later in the string.                        

Use the following strings to test your program.

1. A+ B - C
2. A * B / (C + 9)
3. A * ((B / C) + D + (E - 5)
4. A * (B / C) + D + (E - 9))

Clearly describe the algorithm you will use to determine if the string contains balanced parenthesis. Document the program so I can follow what is going on. The output should look like this:

          String: A + B – C                                No parenthesis

String: A * B / (C+9)                          Matching parenthesis

String: A * ((B / C) + D + (E - 5)          Parenthesis don’t match. Missing right parenthesis

String: A * (B / C) + D + (E - 9))          Parenthesis don’t match. Missing left

parenthesis

Answer 1

Solution:

The algorithm is pretty simple:

Step1: Create a flag equal to 0

Step2: Create a stack and read the expression

Step3: If there is an opening paranthesis set flag =1 and push the paranthesis into stack

Step4: If there is a closing paranthesis check if stack is empty.If stack is empty set flag=-1 and break or else pop the stack.

Step5: Continue untill all the characters are read.

Step6: After exiting the loop if stack is not empty missing right paranthesis else if flag==0 no paranthesis

else if flag==-1 missing right paranthesis else matching paranthesis.

Code:

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

int main()
{
        //Stack to check the balaning of paranthesis
        stack <char> paranthesis;
        //Expression for input
        string expression;
        cout<<"String: ";
        getline(cin,expression);
        //flag to check no paranthesis and missing right paranthesis
        int i=0,flag=0;
        //iterating the expression
        for(i=0;i<expression.length();i++)
        {
                //If opening paranthesis push into stack
                if(expression[i]=='(')
                {
                        //set flag to 1 if paranthesis appears
                        flag=1;
                        paranthesis.push(expression[i]);
                }
                //If closing paranthesis
                else if(expression[i]==')' )
                {
                        //If stack is empty missing left paranthesis set flag=-1 and break
                        if(paranthesis.empty())
                        {
                                flag=-1;
                                break;
                        }
                        //If stack is not empty pop
                        else
                                paranthesis.pop();
                                
                }
                
        }
        //If stack not empty missing right paranthesis
        if(!paranthesis.empty())
        {
                cout<<"\tParenthesis don't match. Missing right parenthesis";
        }
        //if flag is 0 then no paranthesis
        else if(flag==0)
        {
                cout<<"\tNo paranthesis";
        }
        //if flag =-1 missing left paranthesis
        else if(flag==-1)
        {
                cout<<"\tParenthesis don't match. Missing left parenthesis";              
        }
        //if none satisfies the matching paranthesis
        else 
        {
                cout<<"\tMatching paranthesis";
        }
}

the output of 4 sample runs are clubbed together

Output: