Question

C++

Include a Stack class but DO NOT use STL stack, do not sumbit code that is similar to www.cplusplus.com/forum/beginner/192479/

Parenthesis Balance Problem Description Compilers require parenthesis, braces, brackets, and angled brackets to be balanced. This means that every time one is opened it must also be close AND everything between the two are also balanced. Balanced: (00) oO100) (C0O Unbalanced: (DI This is easily determined by creating a stack and reading the input. When an open parenthesis is found, push it to onto the stack. When a closed parenthesis is found, pop the stack and check that the one on the stack is the same as the one found. All other input, letters, numbers, symbols, can be ignored since they do not effect balancing. When the string is finished with no errors and the stack is empty the parenthesis are balanced. (C0) Program Particulars You can create the stack however you want. You may use an array, linked list, or vector It must be able to store the type of parenthesis O<>[and should store at least 20 elements. You should have error checks on the stack for Stack Overflow and Stack Underflow nput: Take in a string that will contain the set of parenthesis to be balanced. Everything will be on one line and there will be no spaces. There may be numbers, letters, and other symbols between the parenthesis, these may be ignored since they have no effect on balancing. Keep taking input until a 0 is entered. Output State whether the set of parenthesis is balanced, or if not balanced show what is missing and show where. Sample Input Enter set: ( (1+2) * (2+3)) +4 Enter set: (1+(2) 3) Enter set: ( () ) { [ ] }< ( ) () [)) Enter set: <>[><)) Enter set: [)))) Enter set: 0 Sample Output: OO)This set is balanced () No closeh | ( ()) { [ ] }<() () [] No close > No close []) Too many close) Exiting

Answer 1

C++ program :-

#include<bits/stdc++.h>
using namespace std;
  
bool is_expr_balanced(string expr)
{
stack<char> s;
char x;
  
// Traversing the Expression
for (int i=0; i<expr.length(); i++)
{
if (expr[i]=='('||expr[i]=='['||expr[i]=='{'||expr[i]=='<')
{
// Push the element in the stack
cout<<expr[i];
s.push(expr[i]);
continue;
}
  
switch (expr[i])
{
case ')':
// Store the top element in a
if (s.empty()){
cout<<" Too many closes "<<expr[i];
return false;
}
x = s.top();
s.pop();
if (x=='{' || x=='[' || x == '<') {
cout<<" No close "<<expr[i]<<endl;
return false;
}
else
cout<<expr[i];
break;
  
case '}':
// Store the top element in b
if (s.empty()){
cout<<" Too many closes "<<expr[i];
return false;
}
x = s.top();
s.pop();
if (x=='(' || x=='[' || x=='<'){
cout<<" No close "<<expr[i]<<endl;
return false;
}
else
cout<<expr[i];
break;
  
case ']':
// Store the top element in c
if (s.empty()){
cout<<" Too many closes "<<expr[i];
return false;
}
x = s.top();
s.pop();
if (x =='(' || x == '{' || x=='<') {
cout<<" No close "<<expr[i]<<endl;
return false;
}
else
cout<<expr[i];
break;
case '>':
// Store the top element in c
if (s.empty()){
cout<<" Too many closes "<<expr[i];
return false;
}
x = s.top();
s.pop();
if (x =='(' || x == '{' || x == '[') {
cout<<" No close "<<expr[i]<<endl;
return false;
}
else
cout<<expr[i];
break;
}
}
  
  
// Check Empty Stack
return (s.empty());
}
  
// Driver program to test above function
int main()
{
string expr;
  
cout<<"Enter set : ";
getline (cin, expr);
cout<<endl;
  
if(expr[0] == '0'){
cout<<"Exiting"<<endl;
return 0;
}
  
if (is_expr_balanced(expr))
cout << " This set is balanced";

return 0;
}

Output :-

Stdin Inputs... Result... CPU Time: 8.8 sec(s), Memory: 3272 kiLobyte(s) Enter set: ◇[ No close >

Stdin Inputs... Result... CPU Time: 8.88 sec(s), Memory: 3276 kilobyte(s) Enter set: [1 Too many closes)

Stdin Inputs... Result... CPU Time: θ.ee sec(s), Memory: 3256 kilobyte(s) Enter set: (()()) This set is balanced

Stdin Inputs... Result... CPU Time: 8.88 sec(s), Memory: 3188 kilobyte(s) Enter set: Exiting