May 14, 2012 – My Programming Notes

Daily Archives: May 14, 2012

C++ || Stack – Using A Stack, Determine If A Set Of Parentheses Is Well-Formed

May 14, 2012 admin 2 Comments

Here is another homework assignment which was presented in a C++ Data Structures course. This assignment was used to introduce the stack ADT, and helped prepare our class for two later assignments which required using a stack. Those assignments can be found here:

(1) Stack Based Infix To Postfix Conversion (Single Digit) (2) Stack Based Postfix Evaluation (Single Digit)

REQUIRED KNOWLEDGE FOR THIS PROGRAM

Stack Data Structure Cin.getline #include "ClassStackListType.h"

A simple exercise for testing a stack is determining whether a set of parenthesis is “well formed” or not. What exactly is meant by that? In the case of a pair of parenthesis, for an expression to be well formed, consider the following table.





		
		
			Well-Formed Expressions             |           Ill-Formed Expressions
------------------------------------|--------------------------------------
( a b c [ ] )                       |             ( a b c [ )
( ) [ ] { }                         |             ( (
{ ( a b c d e ) ( ) }               |             [ a b c d e ) ( ) }
( a + [ b - c ] / d )               |             ( a + [ b - c } /  d )
			
				
					
				
					1
2
3
4
5
6
				
						Well-Formed Expressions             |           Ill-Formed Expressions
------------------------------------|--------------------------------------
( a b c [ ] )                       |             ( a b c [ )
( ) [ ] { }                         |             ( (
{ ( a b c d e ) ( ) }               |             [ a b c d e ) ( ) }
( a + [ b - c ] / d )               |             ( a + [ b - c } /  d )

Given an expression with characters and parenthesis, ( ), [ ], and { }, our class was asked to determine if an expression was well formed or not by using the following algorithm:





		
		
			// An algorithm for a Well Formed expression

Set 'balanced' to true
Set 'symbol' to the first character in the current expression

while(there are more characters AND 'balanced' == true)
{
    if('symbol' is an opening symbol)
    {
        Push 'symbol' onto the stack
    }
    else if('symbol' is a closing symbol)
    {
        if the stack is empty
            'balanced' = false
        else
            Set the 'openSymbol' to the item at the top of the stack
            Pop the stack
            Check to see if 'symbol' matches 'openSymbol'
            (i.e - if openSymbol == '(' and symbol == ')'
            then 'balanced' = true)
    }
    Set 'symbol' to the next character in the current expression
}

if('balanced' == true AND stack is empty)
{
    Expression is well formed
}
else
{
    Expression is NOT well formed
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
				
						// An algorithm for a Well Formed expression
 
Set 'balanced' to true
Set 'symbol' to the first character in the current expression
 
while(there are more characters AND 'balanced' == true)
{
    if('symbol' is an opening symbol)
    {
        Push 'symbol' onto the stack
    }
    else if('symbol' is a closing symbol)
    {
        if the stack is empty
            'balanced' = false
        else
            Set the 'openSymbol' to the item at the top of the stack
            Pop the stack
            Check to see if 'symbol' matches 'openSymbol'
            (i.e - if openSymbol == '(' and symbol == ')'
            then 'balanced' = true)
    }
    Set 'symbol' to the next character in the current expression
}
 
if('balanced' == true AND stack is empty)
{
    Expression is well formed
}
else
{
    Expression is NOT well formed
}// http://programmingnotes.org/

======= WELL-FORMED EXPRESSIONS =======

This program uses a custom template.h class. To obtain the code for that class, click here.





		
		
			Is The Expression Well-Formed?
			
C++
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   May 14, 2012
//    Taken From: http://programmingnotes.org/
//    File:  wellFormed.cpp
//    Description: Demonstrates how to check if an expression is well formed
// ============================================================================
#include <iostream>
#include "ClassStackListType.h"
using namespace std;

// function prototypes
bool IsOpen(char symbol);
bool IsClosed(char symbol);
bool IsWellFormed(char openSymbol, char closeSymbol);

int main()
{
    // declare variables
    char expression[120];
    char openSymbol;
    int index=0;
    bool balanced = true;
    StackListType<char> stack; // this is the stack declaration

    // obtain data from the user using a char array
    cout <<"Enter an expression and press ENTER. "<<endl;
    cin.getline(expression,sizeof(expression));

    cout << "\nThe expression: " << expression;

    // loop thru the char array until we reach the 'NULL' character
    // and while 'balanced' == true
    while (expression[index]!='\0' && balanced)
    {
        // if input is an "open bracket" push onto stack
        // else, process info
        if (IsOpen(expression[index]))
        {
            stack.Push(expression[index]);
        }
        else if (IsClosed(expression[index]))
        {
            if(stack.IsEmpty())
            {
                balanced = false;
            }
            else
            {
                openSymbol = stack.Top();
                stack.Pop();
                balanced = IsWellFormed(openSymbol, expression[index]);
            }
        }
        ++index;
    }

    if (balanced && stack.IsEmpty())
    {
        cout << " is well formed..." << endl;
    }
    else
    {
        cout << " is NOT well formed!!! " << endl;
    }
}// End of Main

bool IsOpen(char symbol)
{
    if ((symbol == '(') || (symbol == '{') || (symbol == '['))
    {
        return true;
    }
    else
    {
        return false;
    }
}// End of IsOpen

bool IsClosed(char symbol)
{
    if ((symbol == ')') || (symbol == '}') || (symbol == ']'))
    {
        return true;
    }
    else
    {
        return false;
    }
}// End of IsClosed

bool IsWellFormed(char openSymbol, char closeSymbol)
{
    return (((openSymbol == '(') && closeSymbol == ')') || ((openSymbol == '{') && closeSymbol == '}')
        || ((openSymbol == '[') && closeSymbol == ']'));
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   May 14, 2012
//    Taken From: http://programmingnotes.org/
//    File:  wellFormed.cpp
//    Description: Demonstrates how to check if an expression is well formed
// ============================================================================
#include <iostream>
#include "ClassStackListType.h"
using namespace std;
 
// function prototypes
bool IsOpen(char symbol);
bool IsClosed(char symbol);
bool IsWellFormed(char openSymbol, char closeSymbol);
 
int main()
{
    // declare variables
    char expression[120];
    char openSymbol;
    int index=0;
    bool balanced = true;
    StackListType<char> stack; // this is the stack declaration
 
    // obtain data from the user using a char array
    cout <<"Enter an expression and press ENTER. "<<endl;
    cin.getline(expression,sizeof(expression));
 
    cout << "\nThe expression: " << expression;
 
    // loop thru the char array until we reach the 'NULL' character
    // and while 'balanced' == true
    while (expression[index]!='\0' && balanced)
    {
        // if input is an "open bracket" push onto stack
        // else, process info
        if (IsOpen(expression[index]))
        {
            stack.Push(expression[index]);
        }
        else if (IsClosed(expression[index]))
        {
            if(stack.IsEmpty())
            {
                balanced = false;
            }
            else
            {
                openSymbol = stack.Top();
                stack.Pop();
                balanced = IsWellFormed(openSymbol, expression[index]);
            }
        }
        ++index;
    }
 
    if (balanced && stack.IsEmpty())
    {
        cout << " is well formed..." << endl;
    }
    else
    {
        cout << " is NOT well formed!!! " << endl;
    }
}// End of Main
 
bool IsOpen(char symbol)
{
    if ((symbol == '(') || (symbol == '{') || (symbol == '['))
    {
        return true;
    }
    else
    {
        return false;
    }
}// End of IsOpen
 
bool IsClosed(char symbol)
{
    if ((symbol == ')') || (symbol == '}') || (symbol == ']'))
    {
        return true;
    }
    else
    {
        return false;
    }
}// End of IsClosed
 
bool IsWellFormed(char openSymbol, char closeSymbol)
{
    return (((openSymbol == '(') && closeSymbol == ')') || ((openSymbol == '{') && closeSymbol == '}')
        || ((openSymbol == '[') && closeSymbol == ']'));
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output
(Note: the code was compile four separate times to display different output)

====== RUN 1 ======
Enter an expression and press ENTER. (( The expression: (( is NOT well formed!!! ====== RUN 2 ====== Enter an expression and press ENTER. (a{b[]}c) The expression: (a{b[]}c) is well formed... ====== RUN 3 ====== Enter an expression and press ENTER. [(7 * 28) - 1987] The expression: [(7 * 28) - 1987] is well formed... ====== RUN 4 ====== Enter an expression and press ENTER. {3 + [2 / 3] - (9 + 18) * 12)
The expression: {3 + [2 / 3] - (9 + 18) * 12) is NOT well formed!!!

Daily Archives: May 14, 2012

C++ || Stack – Using A Stack, Determine If A Set Of Parentheses Is Well-Formed

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories