CplusplusCompiler/TreeNode.cpp at master · adriano515/CplusplusCompiler · 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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

#include <iostream>
#include <stack>
#include "postfix.h"
#include "TreeNode.h"

using namespace std;

/*
Stack for operands
Stack for subtrees (only root nodes woudl be in here)

check left to right
if operand push to stack
if operator check if it's kleen , if not then pop two operands from stack, if it is then pop 1
if there was only 1 popped operand go to subtree stack and pop a subtree
if there was nothing to pop go to subtree stack and pop 2 subtrees
*/

stack <TreeNode*> postfix2Tree(string postfix){

    stack<char> items;
    stack<TreeNode*> subTree;
    stack<TreeNode*> nodes;

    for (int i=0; i < postfix.length(); i++){
        if(isOperand(postfix[i])){
            items.push(postfix[i]);
        }
        else if(isOperator(postfix[i])){
            if (postfix[i]=='^'){

                if (items.size()>=1 ){
                    char izq = items.top();
                    nodes.push(new TreeNode(izq));
                    items.pop();

                    subTree.push(new TreeNode(postfix[i]));
                    subTree.top()->setLeft(nodes.top());
                    nodes.pop();

                    subTree.top()->setValue(postfix[i]);
                }

                else{
                    stack<TreeNode*> temp;
                    temp.push(subTree.top());
                    subTree.pop();
                    subTree.push(new TreeNode(postfix[i]));
                    subTree.top()->setLeft(temp.top());
                    temp.pop();
                }

            }

            else{
                if (items.size() >= 2){
                    char der = items.top();
                    nodes.push(new TreeNode(der));
                    items.pop();

                    char izq = items.top();
                    items.pop();
                    nodes.push(new TreeNode(izq));

                    subTree.push(new TreeNode(postfix[i]));
                    subTree.top()->setLeft(nodes.top());
                    nodes.pop();

                    subTree.top()->setRight(nodes.top());
                    nodes.pop();

                    subTree.top()->setValue(postfix[i]);

            }
                else if (items.size() ==1){

                    stack<TreeNode*> temp;

                    char izq = items.top();
                    items.pop();
                    nodes.push(new TreeNode(izq));

                    temp.push(subTree.top());
                    subTree.pop();

                    subTree.push(new TreeNode(postfix[i]));
                    subTree.top()->setLeft(nodes.top());
                    nodes.pop();

                    subTree.top()->setRight((temp.top()));
                    temp.pop();

                    subTree.top()->setValue(postfix[i]);

                }

                else if (items.size() ==0){
                    stack<TreeNode*> temp;

                    temp.push(subTree.top());
                    subTree.pop();
                    temp.push(subTree.top());
                    subTree.pop();

                    subTree.push(new TreeNode(postfix[i]));
                    if(postfix.size()-1==i and postfix[i]=='*' and temp.top()->getValue()=='^' ){
                                subTree.top()->setLeft(temp.top());
                                temp.pop();
                                subTree.top()->setRight(temp.top());
                                temp.pop();
                    }
                    else {
                        subTree.top()->setRight(temp.top());
                        temp.pop();
                        subTree.top()->setLeft(temp.top());
                        temp.pop();
                    }

                }
            }

        }
    }
    return subTree;
}