Write a C++ program that uses STACK to achieve the following: Complete the main
ID: 3575940 • Letter: W
Question
Write a C++ program that uses STACK to achieve the following:
Complete the main program (below) and determine if the user has provided an expression with a balanced set of parenthesis. The mechanism for checking if the parenthesis is balanced must use STACK.
**********Complete the program below***************
#include<iostream>
#include<string>
using namespace std;
class Stack {
public:
Stack() {
Stack(10);
}
Stack(int capacity) : cap(capacity - 1), top(0) {
data = new char[capacity];
}
~Stack() {
delete data;
}
void push(char value);
char pop();
bool isEmpty();
private:
int top, cap;
char *data;
};
void Stack::push(char value) {
if (top == cap) {
/* Full stack */
return;
}
data[top++] = value;
}
char Stack::pop() {
if (top == 0) {
/* Empty stack */
return '';
}
return data[--top];
}
bool Stack::isEmpty() {
return top == 0;
}
int main(void) {
cout << "Enter an expression" << endl;
string str;
getline(cin, str);
Stack s(15);
for (int i = 0; i < str.length(); i++) {
if (str[i] == ' ') {
continue;
}
/*
* Complete me
*/
}
/*
* Complete me
*/
return 0;
}
SAMPLE OUTPUT:
Enter an expression
1 + 3
Balanced Parenthesis
Press any key to continue . . .
Enter an expression
1 + (3 * 5 - 7
Mismatched Parenthesis
Press any key to continue . . .
Enter an expression
5 * ( 3 + 7 )
Balanced Parenthesis
Press any key to continue . . .
Enter an expression
) + 3 * ( 7 + 4
Mismatched Parenthesis
Press any key to continue . . .
Explanation / Answer
#include<iostream>
#include<string>
using namespace std;
class Stack {
public:
Stack() {
Stack(10);
}
Stack(int capacity) : cap(capacity - 1), top(0) {
data = new char[capacity];
}
~Stack() {
delete data;
}
void push(char value);
char pop();
bool isEmpty();
private:
int top, cap;
char *data;
};
void Stack::push(char value) {
if (top == cap) {
/* Full stack */
return;
}
data[top++] = value;
}
char Stack::pop() {
if (top == 0) {
/* Empty stack */
return '';
}
return data[--top];
}
bool Stack::isEmpty() {
return top == 0;
}
int main(void) {
cout << "Enter an expression" << endl;
string str;
getline(cin, str);
Stack s(15);
for (int i = 0; i < str.length(); i++) {
if (str[i] == ' ') //if the characer at index i is blank space continue the loop
{
continue;
}
else
{
if(str[i]=='(')//if the character at index i is a opening parenthesis then push it into the stack s
{
s.push(str[i]); // push the value in stack
}
else if(str[i]==')')//if the character at index i is a closing parenthesis then pop the top value
{
char exp=s.pop();//store the top value os stack s in char variable exp
if(exp!='(')//if the top value popped is a opening parenthesis then it makes a pair.
{
s.push(exp);//if the top value popped is a closing parenthesis then push the top value back in stack as it did not make a pair.
s.push(str[i]);//now push the closing parenthesis on top.
}
}
}
}
if(s.isEmpty())//at the end of the loop check if the stack s is empty or not
{
cout<<"Balanced Parenthesis";//if it is empty then it means all parenthesises had pairs and all of them cancelled each other
}
else
{
cout<<"Mismatched Parenthesis";//if it is not empty then it means some parenthesises were left without pairs hence they did not cancel each other out.
}
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.