-
Notifications
You must be signed in to change notification settings - Fork 0
/
shuntYard.cpp
133 lines (121 loc) · 3.25 KB
/
shuntYard.cpp
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
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <map>
#include <vector>
#include <cstdlib>
#include <stdexcept>
#include "Operator.h"
#include "Input.h"
#include "Integer.h"
using namespace std;
vector<char> conversion(string x) {
vector<char> data(x.begin(), x.end());
return data;
}
vector<Input*> conversion2(vector<string> rpn){
vector<Input*> input;
for(int i=0; i<rpn.size(); i++){
if(rpn[i]=="+"||rpn[i]=="-"||rpn[i]=="/"||rpn[i]=="*"||rpn[i]=="^"){
input.push_back(new Operator(rpn[i].at(0)));
}
else{ //push the integer
string a = rpn[i];
input.push_back(new Integer(atoi(a.c_str())));
}
}
return input;
}
vector<string> toStringVec(string expr){
vector<string> stringVec;
int count=0;
for(int i =0; i<expr.size();i++){
if((expr.at(i)=='+')||(expr.at(i)=='-')||(expr.at(i)=='/')||(expr.at(i)=='*')||(expr.at(i)=='^')){
stringstream ss;
stringVec.push_back(expr.substr(count,i-count));
ss<<expr.at(i);
stringVec.push_back(ss.str());
ss.str("");
count = i+1;
}
}
if(expr.at(count)){
stringVec.push_back(expr.substr(count, expr.at(expr.size()-1)));
}
return stringVec;
}
vector<string> shuntYard(string x) {
vector<string> expr = toStringVec(x);
vector<string> queue; stack<char> opStack;
map<char, int> opPrec;
opPrec['('] = -1;
opPrec['+'] = 1; opPrec['-'] = 1;
opPrec['*'] = 2; opPrec['/'] = 2;
opPrec['^'] = 3; opPrec['sqrt'] = 3;
bool lastWasOp = true;
for(int i=0;i<expr.size();i++){
if((expr[i]=="+")||(expr[i]=="-")||(expr[i]=="/")||(expr[i]=="*")||(expr[i]=="^")){
switch (expr[i].at(0)) {
case '(':
opStack.push('(');
break;
case ')':
while (opStack.top()!=('(')) {
stringstream ss;
ss<<opStack.top();
queue.push_back(ss.str());
opStack.pop();
}
opStack.pop();
break;
default: //op precedence
{
if (lastWasOp) {
// Convert unary operators to binary in the RPN.
if (expr[i]=="-" || expr[i]=="+") {
queue.push_back("0");
} else {
throw domain_error(
"Unrecognized unary operator.");
}
}
while (!opStack.empty() &&
(opPrec[expr[i].at(0)] <= opPrec[opStack.top()])) //comparing stack operators
{
stringstream ss;
ss<<opStack.top();
queue.push_back(ss.str());
opStack.pop();
}
opStack.push(expr[i].at(0));
lastWasOp = true;
}
}
}
else {
// If the string is a number, add it to the output queue.
queue.push_back(expr[i]);
lastWasOp = false;
}
}
while(!opStack.empty()){ //empty the final stack
stringstream ss;
ss<<opStack.top();
queue.push_back(ss.str());
opStack.pop();
}
return queue;
}
int main(){
string a = "44+44-3/333*99";
vector<string> output = shuntYard(a);
vector<Input*> input = conversion2(output);
//TESTING - cast the subclass upon the superclass to be able to access subclass methods
// Calculator* calc = new Calculator();
// calc->setVec(input);
// calc->solve();
// vector<Input*> result = calc->getVec();
// Integer* test = (Integer*)result[0];
// cout<< test->getInteger();
}