Use either a static or dynamic stack to write a program that checks your express

Question

Use either a static or dynamic stack to write a program that checks your expression for balanced parentheses, brackets and braces. Make sure that you identify the following cases: (a) balanced expression, (b) too many opening symbols, (c) too many closing symbols, (d) unmatched types

using this algothrim: Start with an empty stack and scan an expression from right to left.

Whenever we encounter an opening symbol (a left parenthesis, left bracket or left brace), push it onto a stack.

Whenever we encounter a closing symbol a (right parenthesis, right bracket or right brace), pop an item off the stack and check to see that its type matches the type of the current closing symbol.

If the stack is empty by the time when we get to the end of the expression, and if all pairs of opening/closing symbols match, the expression is balanced.)

Check your program for the following sequences:

a.{ [ [ ( ) ( ) ] [ ( ) ] ( ) }

b.{ [ ( ) ) ( ) ] }

c.{ [ [ [ ( ) ( ) ] }

d.{ [ ( ) ( ) } ]

Explanation / Answer

#include <iostream>
#include <string>

using namespace std;

#include <string>
using namespace std;

class Stack {
private:
   int top;
   int capacity;
   int numused;
   char *storage;
public:
   Stack() {
       capacity = 100;
       storage = new char[capacity];
       this->capacity = capacity;
       numused = 0;
       top = -1;
   }

   void doublesize(){
       capacity *= 2;
       char *newarr = new char[capacity];
       for (int i = 0; i < capacity; ++i){
           newarr[i] = storage[i];
       }
   }

   void push(char value) {
       if (top == capacity)
           doublesize();
       top++;
       storage[top] = value;
   }

   char peek() {
       if (top == -1)
           throw string("Stack is empty");
       return storage[top];
   }

   void pop() {
       if (top == -1)
           throw string("Stack is empty");
       top--;
   }

   bool isEmpty() {
       return (top == -1);
   }

   ~Stack() {
       delete[] storage;
   }
};

bool checksequence(string seq){
   Stack s = Stack();
   for (int i = 0; i < seq.size(); ++i){
       if (seq[i] == ' '){
           continue;
       }
       if (i < seq.size()){
           if (seq[i] == '{' || seq[i] == '[' || seq[i] == '('){
               s.push(seq[i]);
           }
           if (seq[i] == '}'){
               if (s.peek() != '{'){
                   if (i != seq.size() - 1){
                       return false;
                   }
               }
               else{
                   s.pop();
               }
           }
           if (seq[i] == ']'){
               if (s.peek() != '['){
                   if (i != seq.size() - 1){
                       return false;
                   }
               }
               else{
                   s.pop();
               }
           }
           if (seq[i] == ')'){
               if (s.peek() != '('){
                   if (i != seq.size() - 1){
                       return false;
                   }
               }
               else{
                   s.pop();
               }
           }
       }
   }
   return true;
}

int main(){
   string sequences[] = { "{ [ [ ( ) ( ) ] [ ( ) ] ( ) }", "{ [ ( ) ) ( ) ] }", "{ [ [ [ ( ) ( ) ] }", "{ [ ( ) ( ) } ]" };
   for (int i = 0; i < 4; ++i){
       if (checksequence(sequences[i])){
           cout << sequences[i] << " is a valid sequence" << endl;
       }
       else{
           cout << sequences[i] << " is not a valid sequence" << endl;
       }
       cout << endl;
   }
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.