Parenthesis-Matching/Parenthesis Matching.cpp at main · RezaGooner/Parenthesis-Matching · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <string>

using namespace std ;

const int MAX_SIZE = 100;


struct Stack {
    int top; // index of top of stack
    string elements[MAX_SIZE];
};

bool isEmpty(Stack& stack) {
    if (stack.top == -1){
        return true ;
    }
    return false ;
}

bool isFull(Stack& stack) {
    if (stack.top == MAX_SIZE - 1){
        return true ;
    }
    return false ;
}

void push(Stack& stack, string value) {
    if (isFull(stack)) {
        cout << "Stack overflow!" << endl;
        return;
    }
    stack.elements[++stack.top] = value ;
}

void pop(Stack& stack) {
    if (isEmpty(stack)) {
        cout << "Stack underflow!" << endl;
        return;
    }
    stack.elements[stack.top--] = "" ;
}

string top(Stack& stack) {
    if (isEmpty(stack)) {
        //cout << "Stack is empty!" << endl;
        return "";
    }
    return stack.elements[stack.top];
}

bool parenthesisMatching(Stack& stack , string phrase){
    for (int i = 0 ; i < phrase.size() ; i++){
        if (phrase[i] != '{' && phrase[i] != '}' && phrase[i] != '(' && phrase[i] != ')' && phrase[i] != '[' && phrase[i] != ']'){
            continue ;
        }
        switch (phrase[i]) {
            case ')' :
                if (top(stack) == "(" ){
                    pop(stack);
                }
                else {
                    push(stack , string(1, phrase[i]));
				}
                break ;

            case ']' :
                if (top(stack) == "[" ){
                    pop(stack);
                }
                else {
                    push(stack , string(1, phrase[i]));
				}
                break ;

            case '}' :
                if (top(stack) == "{" ){
                    pop(stack);
                }
                else {
                    push(stack , string(1, phrase[i]));
				}
                break ;

            default :
                push(stack , string(1, phrase[i]));
        }
    }
    if (isEmpty(stack)){
        return true ;
    }
    return false ;
}

int main() {
    Stack stack;
    stack.top = -1;
    string str ;
    cout << "Enter the phrase : " ;
    cin >> str ;
    if (parenthesisMatching(stack , str )){
    	cout << "True" ;
	} else {
		cout << "False" ;
	}

    return 0;
}