Balanced Brackets
From the first assignment it is known that at ancient Val E Community College, an evil computer science instructor named Genghis Khent delighted in tormenting his Data Structures students with apparently unsolvable questions on data structures. Being a community college instructor, he also was always looking for more ways to make money, especially since he had a free source of programming labor, his Data Structures students.
Genghis Khent thought he could make money with a new programming language, G++ (the G being for Genghis of course). He told his hapless Data Structures students to write a G++ compiler.
The G++ programming language uses only 6 characters, left and right brackets, parentheses and curly braces: {[ ( } ] ). A left curly brace, bracket or parentheses is referred to as a left character. A right curly brace, bracket or parentheses is referred to as a right character.
A G++ expression is valid if each left character in the expression “matches” with a corresponding right character in the expression. The test for a match requires going left to right through an expression, character by character. When a right character is encountered, then it is compared to the rightmost left character that was not previously compared to a right character. If the characters match, such as { and }, [ and ], or ( and ),then you continue through the expression, comparing each right character to the rightmost left character that was not previously compared to a right character, until either the left and right characters don’t match (which means the expression is not valid) or there are no more right characters. When there are no more right characters, if all of the left characters have previously been compared to a right character, the expression is valid. However, if there still are left characters that have not previously been compared to a right character, the expression is invalid.
Program Description
Your program, which will be written in C++, not G++, will prompt the user to enter a string of not more than20 characters. You may use a character array, a C-string or the C++ string class; the choice is up to you. You can assume the user enters no more than 20 characters (though the user may enter less than 20 characters) and the characters entered are limited to left and right brackets, parentheses and curly braces; you do not need to do any error-checking on this. After the user ends input, by the Enter key, the program checks if the string is a valid G++ expression, and reports that it either is or isn’t. Sample outputs:
Enter an expression: []{}()
It’s a valid expression
Enter an expression: ()[{}]
It’s a valid expression
Enter an expression: [({)}]
It’s NOT a valid expression
Stack Class
Explains a stack and how it will be represented by a class having the member variables and member functions (including a constructor) appropriate for a stack.
Multiple Files
The class will be written using header and implementation files. Your program also will include a driver file, so your multi-file project will have three files:
File Name Purpose
cstack.h Header file for stack
cstack.cpp Implementation file for stack
test.cpp Driver file
Solution:
cstack.h
class CStack {
public:
CStack(); // Constructor. Always public
bool IsEmpty(); // this function could be private
bool IsFull(); // ditto
int top;
char data[21];
};
cstack.cpp
#include “cstack.h”
bool CStack::IsEmpty ()
{
return (top == -1);
}
CStack::CStack()
{
top = -1;
}
bool CStack::IsFull()
{
return (top == 20);
}
test.cpp
#include “cstack.h”
#include
#include
using namespace std;
bool isMatchingPair(char character1, char character2)
{
if (character1 == ‘(‘ && character2 == ‘)’)
return 1;
else if (character1 == ‘{‘ && character2 == ‘}’)
return 1;
else if (character1 == ‘[‘ && character2 == ‘]’)
return 1;
else
return 0;
}
bool isValidExpression (CStack, char*);
int main (void)
{char expression[21]; // allocate memory for user string input
cout<< “Enter an expression: “;
cin >>expression;
CStack stack1; // creates an instance of a stack (stack1) using class constructor
if (isValidExpression (stack1, expression))
/* This calls the isValidExpression function (which you still need to write) to
fill the data array of the stack. The parameter is the stack instance stack1 */
cout << “\nIt’s a valid expression”;
else
cout << “\nIt’s NOT a valid expression”;
return 0;
}
bool isValidExpression (CStack stackA, char* strExp)
{
// code goes here
int i = 0;
while (strExp[i])
{
if (strExp[i] == ‘{‘ || strExp[i] == ‘(‘ || strExp[i] == ‘[‘ && !stackA.IsFull())
stackA.data[++stackA.top] = strExp[i];
if (strExp[i] == ‘}’ || strExp[i] == ‘)’ || strExp[i] == ‘]’)
{
if (stackA.IsEmpty())
return 0;
else if ( !isMatchingPair(stackA.data[stackA.top–], strExp[i]) )
return 0;
}
i++;
}
if (stackA.IsEmpty())
return 1; /*balanced*/
else
return 0; /*not balanced*/
}
// end of driver file