-
Notifications
You must be signed in to change notification settings - Fork 0
/
Rational.h
202 lines (170 loc) · 4.87 KB
/
Rational.h
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
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;
class Rational {
friend class Expression;
long long int m_num, m_den;
public:
Rational(long long int num = 0, long long int den = 1) {
m_num = num;
m_den = den;
}
Rational getResult();
void simplify(); // simplifies rational numbers to their lowest forms
// overloaded operators: +, -, *, /
Rational operator+(Rational rat);
Rational operator-(Rational rat);
Rational operator*(Rational rat);
Rational operator/(Rational rat);
};
class Expression {
string exp;
//Rational obj;
public:
Expression(string exp);
string getExpression(); // returns this->exp
int precedence(char op); // defines and checks precedence
Rational eval(Rational rat1, Rational rat2, char op); // evaluates a single operation
Rational evaluate(); // evaluates the entire expression
void getResult(); // prints the result of expression
};
// predefining containers
typedef stack<Rational> stack_rat;
typedef stack<char> stack_op;
Expression::Expression(string exp) {
this->exp = exp;
}
string Expression::getExpression() {
return this->exp;
}
void Expression::getResult() {
Rational res = evaluate();
if (res.m_den != 1)
cout << res.m_num << "/" << res.m_den << endl;
else
cout << res.m_num << endl;
}
int Expression::precedence(char op) {
if (op == '*' || op == '/') return 1;
if (op == '+' || op == '-') return 0;
return -1;
}
void Rational::simplify() {
// solves negative denominator
if (m_den < 0) {
m_num *= -1;
m_den *= -1;
}
long long int den = __gcd(m_num, m_den); // __gcd found in algorithm
m_num /= den;
m_den /= den;
}
Rational Rational::getResult() {
Rational res;
res.m_num = this->m_num;
res.m_den = this->m_den;
return res;
}
Rational Rational::operator+(Rational rat) {
Rational res;
res.m_num = this->m_num * rat.m_den + rat.m_num * this->m_den;
res.m_den = this->m_den * rat.m_den;
return res;
}
Rational Rational::operator-(Rational rat) {
Rational res;
res.m_num = this->m_num * rat.m_den - rat.m_num * this->m_den;
res.m_den = this->m_den * rat.m_den;
return res;
}
Rational Rational::operator*(Rational rat) {
Rational res;
res.m_num = this->m_num * rat.m_num;
res.m_den = this->m_den * rat.m_den;
return res;
}
Rational Rational::operator/(Rational rat) {
Rational res;
res.m_num = this->m_num * rat.m_den;
res.m_den = this->m_den * rat.m_num;
return res;
}
Rational Expression::eval(Rational rat1, Rational rat2, char op) {
Rational res;
switch (op) {
case '+':
res = rat1 + rat2;
break;
case '-':
res = rat1 - rat2;
break;
case '*':
res = rat1 * rat2;
break;
case '/':
res = rat1 / rat2;
break;
}
res.simplify();
return res;
}
Rational Expression::evaluate() {
stack_rat rat; // ratinal number stack
stack_op op; // operator stack
for (int i = 0; i < exp.length(); i++) {
if (exp[i] == ' ') continue; // ignore whitespaces
else if (exp[i] == '(') op.push(exp[i]);
else if (isdigit(exp[i])) {
string str = "";
// continues until you encounter anything other than numbers
while (i < exp.length() && isdigit(exp[i])) {
str += exp[i];
i++;
}
Rational e(stoi(str));
rat.push(e);
i--;
}
// this block evaluates in between parentheses; starts when a closing parentheses is found
else if (exp[i] == ')') {
while (!op.empty() && op.top() != '(') {
Rational rat2(rat.top());
rat.pop();
Rational rat1(rat.top());
rat.pop();
char ope = op.top();
op.pop();
rat.push(eval(rat1, rat2, ope));
}
if (!op.empty()) {
op.pop();
}
}
// checks for precedence and evaluates using rational stack and operator stack
else {
while (!op.empty() && precedence(op.top()) >= precedence(exp[i])) {
Rational rat2(rat.top());
rat.pop();
Rational rat1(rat.top());
rat.pop();
char ope = op.top();
op.pop();
rat.push(eval(rat1, rat2, ope));
}
op.push(exp[i]);
}
}
// evaluates with the leftover operands and operators
while (!op.empty()) {
Rational rat2(rat.top());
rat.pop();
Rational rat1(rat.top());
rat.pop();
char ope = op.top();
op.pop();
rat.push(eval(rat1, rat2, ope));
}
return rat.top();
}