Created
September 20, 2017 02:54
-
-
Save hckim16/42aecaea52761daf9aa94b1c28c520d0 to your computer and use it in GitHub Desktop.
Code to match parentheses - Used information and knowledge from mycodeschool's youtube video at https://www.youtube.com/watch?v=QZOLb0xHB_Qto
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <string> | |
using namespace std; | |
class RuntimeException{ // generic run-time exception for empty stack | |
private: | |
string errorMsg; | |
public: | |
RuntimeException(const string& err) {errorMsg = err;} | |
string getMessage() const {return errorMsg;} | |
}; | |
class StackEmpty:public RuntimeException{ // empty stack | |
public: | |
StackEmpty(const string& err):RuntimeException(err){} | |
}; | |
class Snode{ // Singly Linked List Node | |
public: | |
char elem; // Linked list element value | |
Snode *next; //next item in the list | |
friend class SLinkedList; // provide SLinkedList access | |
}; | |
class SLinkedList{ // Singly Linked List | |
public: | |
SLinkedList(); // empty list constructor | |
~SLinkedList(); //destructor | |
bool empty() const; //is list empty? | |
const char& front() const; //return front element | |
void addFront(const char& e); // add to front of list | |
void removeFront(); //remove front item from list | |
friend class LinkedStack; // give LinkedStack access | |
private: | |
Snode *head; // head of list | |
}; | |
Snode *head; | |
SLinkedList::SLinkedList() // constructor | |
:head(NULL) {} | |
bool SLinkedList::empty() const{ // is list empty? | |
return head == NULL;} | |
const char& SLinkedList::front() const{ // return front element | |
return head-> elem;} | |
SLinkedList::~SLinkedList(){ // destructor | |
while(!empty()) removeFront();} | |
void SLinkedList::addFront(const char& e){ // add to front of list | |
Snode *v = new Snode; // create a new node | |
v-> elem = e; // store data | |
v-> next = head; // head now follows v | |
head = v; // v is now head | |
} | |
void SLinkedList::removeFront(){ // remove front item | |
Snode *old = head; // save the current head | |
head = old-> next; // skip over old head | |
delete old; // delete old head | |
} | |
class LinkedStack{ // create stack element | |
public: | |
LinkedStack(); // constructor | |
int size() const; // number of items in stack | |
bool empty() const; // is stack empty? | |
const char& top() const throw(StackEmpty); // top element | |
void push(const char& e); // push element onto stack | |
void pop() throw(StackEmpty); // pop the stack | |
private: | |
SLinkedList S; // linked list of elements | |
int n; // number of elements | |
}; | |
LinkedStack::LinkedStack() // constructor | |
: S(), n(0) {} | |
int LinkedStack::size() const{ // number of items in the stack | |
return n;} | |
bool LinkedStack::empty() const{ // is stack empty? | |
return n == 0;} | |
const char& LinkedStack::top() const throw(StackEmpty){ // get the top element | |
if(empty()) throw StackEmpty("Top of empty stack"); | |
return S.front(); | |
} | |
void LinkedStack::push(const char& e){ // push element onto stack | |
++n; | |
S.addFront(e); | |
} | |
void LinkedStack::pop() throw(StackEmpty){ // push element onto stack | |
if(empty()) throw StackEmpty("Pop from empty stack"); | |
--n; | |
S.removeFront(); | |
} | |
bool ArePair(char opening,char closing) // check for matching type | |
{ | |
if(opening == '(' && closing == ')') return true; | |
else if(opening == '{' && closing == '}') return true; | |
else if(opening == '[' && closing == ']') return true; | |
return false; | |
} | |
bool ParenMatch(string e){ // check for matching openings and closings | |
LinkedStack P; | |
for(int i = 0; i < e.length(); i++) | |
{ | |
if(e[i] == '(' || e[i] == '{' || e[i] == '[') | |
P.push(e[i]); | |
else if(e[i] == ')' || e[i] == '}' || e[i] == ']') | |
{ | |
if(P.empty() || !ArePair(P.top(),e[i])) | |
return false; | |
P.pop(); | |
} | |
} | |
if (P.empty()) | |
return true; | |
else | |
return false; | |
} | |
int main() | |
{ | |
string expression; | |
cout << "Enter an expression: "; | |
cin >> expression; | |
LinkedStack Paren; | |
if(ParenMatch(expression)) | |
cout << "Balanced\n"; | |
else | |
cout << "Not Balanced\n"; | |
return 0; | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment