Question
b) Given the class ArrayStack, write a full program that would take in an arbitrary string of parentheses, curly braces, and square braces, and outputs
b) Given the class ArrayStack, write a full program that would take in an arbitrary string of parentheses, curly braces, and square braces, and outputs if the string is balanced or not. The string is said to be balanced if all opening elements have a matching closing element of the same type. e.g. The string ( [ ] { } { } { ( ) } ) would be considered balanced, but ( { ) [ ( ] ) ) would not. Refer to Section 5.1.7 (pg 204-205) in your textbook for the algorithm.
Answer:
#include
#include
#include "ArrayStack.h"
int main( ) {
// set up the stack, string, and flag variables
ArrayStack
string input = "";
bool unbalanced = false;
// get the string
cin >> input;
// run through the loop
for (int i =0; i < input.length() && !unbalanced; i++) {
// Your code goes here.
}
// report to the user
cout << "The string is " << (unbalanced ? "unbalanced" : "balanced") << endl;
return 0;
}
#pragma once // Code based on:
// Data Structures and Algorithms in C++, Goodrich, Tamassia, and Mount, 2nd Ed., 2011.
//
#pragma once #include
using namespace std;
template
class ArrayStack { enum { DEF_CAPACITY = 100 }; // default stack capacity
public: ArrayStack(int cap = DEF_CAPACITY); // constructor from capacity int size() const; // number of items in the stack bool empty() const; // is the stack empty? const E& top() const; // get the top element void push(const E& e); // push element onto stack void pop(); // pop the stack void printAll(); // print all elements on stack to cout
private: // member data E* S; // array of stack elements int capacity; // stack capacity int t; // index of the top of the stack };
template ArrayStack::ArrayStack(int cap)
: S(new E[cap]), capacity(cap), t(-1) { } // constructor from capacity
template int ArrayStack::size() const
{ return (t + 1); } // number of items in the stack
template bool ArrayStack::empty() const
{ return (t < 0); } // is the stack empty?
template // return top of stack
const E& ArrayStack::top() const { if (empty()) throw length_error("Top of empty stack"); return S[t]; }
template // push element onto the stack
void ArrayStack::push(const E& e) { if (size() == capacity) throw length_error("Push to full stack"); S[++t] = e; }
template // pop the stack
void ArrayStack::pop() {
if (empty()) throw length_error("Pop from empty stack"); --t;
}
// print all elements on stack
template
void ArrayStack::printAll() {
if (empty()) throw length_error("Empty stack"); cout << "Elements in stack: "; for (int i = t; i >= 0; i--) { cout << "{" << S[i] << "} "; } cout << endl;
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started