Part II-B \"Client vs. Provider\": In Part-II-B, you will play the role of stack
ID: 3859066 • Letter: P
Question
Part II-B "Client vs. Provider": In Part-II-B, you will play the role of stack "client" -- you will write a program which uses the stack module to achieve a goal and expresses its algorithm in terms of the stack primitives.
The Program:
Write a program called balanced that does the following: Prompts the user for a string (see the get_string function from simpleio).
Determines if the given string is a balanced combination of the following six symbols: ( ) { } [ ]
Examples of balanced strings: () (()) ()() {()()} [] [()[]{}]()
Examples of unbalanced strings: ( {}} ()[} [()} )
Program Behavior: The program takes no command-line arguments. When run it prompts the user for a string and then reports if it is legal or not. It then terminates.
Examples: $ ./balanced enter a string: {{}}()(){} this string is balanced. Goodbye. $ ./balanced enter a string: {{)}()(){} this string is not balanced. Goodbye. Notes: Formal definition of a balanced string: (BASIS) The empty string is balanced (in C, a string of length zero) (NESTING) If S is a balanced string, then: (S) is also a balanced string {S} is also a balanced string and [S] is also a balanced string. (CONCATENATION) If A and B are both balanced strings, then AB is also a balanced string. A string is balanced if and only if it can be generated by a sequence of application of the above rules. Extraneous characters: If the given string contains any characters other than the six characters, ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’, it should be automatically considered not balanced / not legal for the purposes of this assignment. Compilation: You have been given a makefile which should simplify compilation. You should be able to simply type "make balanced" to create your executable.
Explanation / Answer
#include <iostream>
#include <stack>
using namespace std;
int main()
{
cout << "Enter the input string ";
string s;
cin >> s;
stack<char> st;
// char a, b, c;
// Traversing the Expression
bool flag = true;
for (int i=0; i<s.length(); i++)
{
// cout << s[i] << " ";
char c = s[i];
if (c =='(' || c=='[' || c =='{')// check if open bracket then add it to stack
{
// Push the element in the stack
st.push(c);
}
else
{
if(c == ')')
{
// Store the top element in a
char a = st.top();
st.pop();
if (a=='{'||a=='[')
{
// cout<<"String is not Legal";
flag = false;
break;
}
}
if(c == '}')
{
// Store the top element in b
char b = st.top();
st.pop();
if (b=='('||b=='[')
{
flag = false;
// cout<<"String is not Legal";
break;
}
}
if(c == ']')
{
// Store the top element in e
char e=st.top();
st.pop();
if (e=='('||e=='{')
{
flag = false;
// cout<<"String is not Legal";
break;
}
}
}
// cout << st.top() << " ";
}
// Check Empty Stack
if (!st.empty() || flag == false)
cout << "String is not Legal";
else
cout << "String is Legal";
return 0;
}