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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
#include<iostream>
#include<string>
#include "StackType.h"
using namespace std;
struct node;
int priority(char);
node* makeNode(char);
void attachOperator(StackType<node*>&, StackType<node*>&);
//Pops operator off of the operators stack,
//Pops 2 operands of treenode stack and attaches them to operator
int evaluateTree(node*);
void printTree (node *root);
void Footer();
struct node{
char info;
node* left;
node* right;
node* parent;
};
int main(){
string infix; // the infix exp<b></b>ression read from the line
StackType<char> input; // stack for input string
StackType<node*> operators; // stack for operator pointer addresses
StackType<node*> treenodes; // stack for output node pointer addresses
char temp,again=' ';
cout << "-Infix to Exp<b></b>ression Tree Creator-" << endl;
cout << "-An exp<b></b>ression tree is created from a user inputted infix exp<b></b>ression-" << endl;
while (again!='n')
{
cout << endl << "Please enter an Infix Mathematical Exp<b></b>ression" << endl;
cin >> infix;
//Pushes the contents of the string into the input stack
for (int i=0;i<infix.length();i++){
input.Push(infix[i]);
}
// While the input stack is not empty...
while(!input.IsEmpty()){
temp=input.Top();
input.Pop();
//If it is operand, make it into a node, add it to output string.
if (isdigit(temp))
treenodes.Push(makeNode(temp));
//If it is Closing parenthesis, make into node, push it on stack.
if (temp==')')
operators.Push(makeNode(temp));
//If it is an operator, then
if ((temp=='+') || (temp=='/') || (temp =='-') || (temp=='*')) {
bool pushed = false;
while(!pushed){
//If stack is empty, make node and push operator on stack.
if(operators.IsEmpty()){
operators.Push(makeNode(temp));
pushed=true;
}
//If the top of stack is closing parenthesis, make node and push operator on stack.
else if (operators.Top()->info ==')'){
operators.Push(makeNode(temp));
pushed=true;
}
//If it has same or higher priority than the top of stack, make node and push operator on stack.
else if ((priority(temp)>priority(operators.Top()->info)) || (priority(temp)==priority(operators.Top()->info))){
operators.Push(makeNode(temp));
pushed=true;
}
//Else pop the operator from the stack, perform attachOperator and add it to treenodes. repeat step 5.
else {
attachOperator(treenodes,operators);
}
}
}
//If it is a opening parenthesis, pop operators from stack and perform attachOperator
//until a closing parenthesis is encountered. Pop and discard the closing parenthesis.
if (temp=='('){
while (operators.Top()->info!=')')
{
attachOperator(treenodes,operators);
}
operators.Pop(); // ')' is popped and discarded
}
}
//If there is no more input, unstack the remaining operators and perform attachOperator
while(!operators.IsEmpty()){
printTree();
attachOperator(treenodes,operators);
}
int answer = evaluateTree(treenodes.Top());
cout << endl << "Evaluation: " << answer << endl;
cout << endl;
printTree();
cout << "Would you like to convert another exp<b></b>ression? (y/n)";
cin >> again;
}
cout << endl;
system("pause");
return 0;
}
//Determines the priority of an operator
int priority(char op){
if ((op =='+') || (op =='-'))
return 1;
if ((op =='/') || (op =='*'))
return 2;
}
//Places a char from the input stack into a new treenode
node* makeNode(char info){
node* childnode;
childnode = new node;
childnode->info = info;
childnode->left = NULL;
childnode->right = NULL;
return childnode;
}
// This is the recursive function I've found, but still I'm not sure if this is what's needed.
void printTree (node *root) {
node* curr=root;
do {
cout<<curr->info<<" ";
curr=curr->parent;
}while (curr!=NULL);
if (curr->left!=NULL) {
printTree(curr->left);
}
if (curr->right!=NULL) {
printTree(curr->right);
}
}
//Pops an operator from a stack
//Builds a tree node with the top two nodes in the
//treenode stacks as its left and right children.
void attachOperator(StackType<node*>& treenodes, StackType<node*>& operators){
node* operatornode = operators.Top();
operators.Pop();
operatornode->left = treenodes.Top();
treenodes.Pop();
operatornode->right = treenodes.Top();
treenodes.Pop();
treenodes.Push(operatornode);
}
//Using a recursive function, the value of the exp<b></b>ression is Calculated
int evaluateTree(node* treenode){
int x,y,z;
if ((treenode->info) == '+'||(treenode->info) == '-'||(treenode->info) == '*'||(treenode->info) == '/') {
x = evaluateTree(treenode->left);
y = evaluateTree(treenode->right);
if (treenode->info=='+')
z=x+y;
else if (treenode->info=='-')
z=x-y;
else if (treenode->info=='*')
z=x*y;
else if (treenode->info=='/')
z=x/y;
return z;
}
else return treenode->info - '0';
}
|
