patterncppMinor
Optimize shunting-yard algorithm
Viewed 0 times
yardalgorithmshuntingoptimize
Problem
Following your suggestions, I updated my expression evaluator with a Shunting-Yard algorithm.
I've created two classes, a Shunting-yard class and a RPNsolver class.
The first I mentioned converts from infix to postfix notation and the other solves the postfix expression.
I'm open to suggestions of any type.
Shunting_yard.h
Shunting_yard.cpp
```
#include "Shunting_yard.h"
Shunting_yard::Shunting_yard(std::string str)
{
this->infix = str;
}
bool Shunting_yard::isoperator(char c)
{
return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}
void Shunting_yard::convert()
{
std::stack operators;
std::istringstream iss(infix);
char tmp;
double num;
while ((int)iss.tellg() != EOF)
{
char token = iss.peek();
if (isdigit(token))
{
iss >> num;
std::stringstream ss;
ss > tmp;
}
else if (token == '(')
{
operators.push(token);
iss >> tmp;
}
else if (token == ')')
{
while (operators.top() != '(')
{
postfix += operators.top();
postfix += " ";
operators.pop();
}
operators.pop();
iss >> tmp;
}
else iss.get(tmp);
}
if (!operators.empty())
{
int size = operators.size();
for (int i = 0; i < size; i++)
{
postfix += operator
I've created two classes, a Shunting-yard class and a RPNsolver class.
The first I mentioned converts from infix to postfix notation and the other solves the postfix expression.
I'm open to suggestions of any type.
Shunting_yard.h
#pragma once
#include
#include
#include
#include
#include
class Shunting_yard
{
private:
std::string infix;
std::map> op //Operators features(precedence, right associative)
{
{ '+', std::make_pair(2, 0) },
{ '-', std::make_pair(2, 0) },
{ '*', std::make_pair(3, 0) },
{ '/', std::make_pair(3, 0) },
{ '^', std::make_pair(4, 1) }
};
bool isoperator(char);
public:
Shunting_yard(std::string );
void convert();
std::string postfix;
};Shunting_yard.cpp
```
#include "Shunting_yard.h"
Shunting_yard::Shunting_yard(std::string str)
{
this->infix = str;
}
bool Shunting_yard::isoperator(char c)
{
return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}
void Shunting_yard::convert()
{
std::stack operators;
std::istringstream iss(infix);
char tmp;
double num;
while ((int)iss.tellg() != EOF)
{
char token = iss.peek();
if (isdigit(token))
{
iss >> num;
std::stringstream ss;
ss > tmp;
}
else if (token == '(')
{
operators.push(token);
iss >> tmp;
}
else if (token == ')')
{
while (operators.top() != '(')
{
postfix += operators.top();
postfix += " ";
operators.pop();
}
operators.pop();
iss >> tmp;
}
else iss.get(tmp);
}
if (!operators.empty())
{
int size = operators.size();
for (int i = 0; i < size; i++)
{
postfix += operator
Solution
This already looks really nice, however it seems there are some minor typos etc.
-
Sort includes alphabetically. That way it is much easier to see whether one is missing.
-
You should make postfix private and add a getter for it
-
You might want to contify and pass per reference the input string.
-
It would not really affect performance but you can simplify your
-
Your isdigit function is missing, but you can take the standard one from cctype
-
Your digit is from a single char, why are you putting it into a double? int would be mor approriate. Also you can utilize std::to_string
-
Never mingle single line if/else with other ones. That completely demolishes the readability of your code.
-
The for loop at the end is unnecessary. Just make a while as long as operators is nonempty.
This gets me to the following
Shunting_yard.h
Shunting_yard.cpp
So much for shunting yard, i might get back to RPN later
-
Sort includes alphabetically. That way it is much easier to see whether one is missing.
-
You should make postfix private and add a getter for it
-
You might want to contify and pass per reference the input string.
-
It would not really affect performance but you can simplify your
isoperator by utilizing op.find(c) != op.end()-
Your isdigit function is missing, but you can take the standard one from cctype
-
Your digit is from a single char, why are you putting it into a double? int would be mor approriate. Also you can utilize std::to_string
-
Never mingle single line if/else with other ones. That completely demolishes the readability of your code.
-
The for loop at the end is unnecessary. Just make a while as long as operators is nonempty.
This gets me to the following
Shunting_yard.h
#pragma once
#include
#include
#include
#include
#include
#include
class Shunting_yard
{
private:
const std::string infix;
std::string postfix;
std::map> op //Operators features(precedence, right associative)
{
{ '+', std::make_pair(2, 0) },
{ '-', std::make_pair(2, 0) },
{ '*', std::make_pair(3, 0) },
{ '/', std::make_pair(3, 0) },
{ '^', std::make_pair(4, 1) }
};
bool isoperator(char) const;
public:
Shunting_yard(const std::string& input);
const std::string& getPostfix() const;
void convert();
};Shunting_yard.cpp
#include "Shunting_yard.h"
Shunting_yard::Shunting_yard(const std::string& input)
: infix(input) {}
bool Shunting_yard::isoperator(char c) const
{
return op.find(c) != op.end();
}
void Shunting_yard::convert()
{
std::stack operators;
std::istringstream iss(infix);
char tmp;
int num;
while ((int)iss.tellg() != EOF)
{
char token = iss.peek();
if (std::isdigit(token))
{
iss >> num;
postfix += std::to_string(num);
postfix += " ";
}
else if (isoperator(token))
{
char o1 = token;
bool offset = 0;
if (!op[o1].second)
offset = 1;
if (!operators.empty())
{
char top = operators.top();
while (isoperator(top))
{
if (op[o1].first > tmp;
}
else if (token == '(')
{
operators.push(token);
iss >> tmp;
}
else if (token == ')')
{
while (operators.top() != '(')
{
postfix += operators.top();
postfix += " ";
operators.pop();
}
operators.pop();
iss >> tmp;
}
else iss.get(tmp);
}
while (!operators.empty()) {
postfix += operators.top();
postfix += " ";
operators.pop();
}
}So much for shunting yard, i might get back to RPN later
Code Snippets
#pragma once
#include <cctype>
#include <iostream>
#include <map>
#include <sstream>
#include <stack>
#include <string>
class Shunting_yard
{
private:
const std::string infix;
std::string postfix;
std::map<char, std::pair<int, bool>> op //Operators features(precedence, right associative)
{
{ '+', std::make_pair(2, 0) },
{ '-', std::make_pair(2, 0) },
{ '*', std::make_pair(3, 0) },
{ '/', std::make_pair(3, 0) },
{ '^', std::make_pair(4, 1) }
};
bool isoperator(char) const;
public:
Shunting_yard(const std::string& input);
const std::string& getPostfix() const;
void convert();
};#include "Shunting_yard.h"
Shunting_yard::Shunting_yard(const std::string& input)
: infix(input) {}
bool Shunting_yard::isoperator(char c) const
{
return op.find(c) != op.end();
}
void Shunting_yard::convert()
{
std::stack<char> operators;
std::istringstream iss(infix);
char tmp;
int num;
while ((int)iss.tellg() != EOF)
{
char token = iss.peek();
if (std::isdigit(token))
{
iss >> num;
postfix += std::to_string(num);
postfix += " ";
}
else if (isoperator(token))
{
char o1 = token;
bool offset = 0;
if (!op[o1].second)
offset = 1;
if (!operators.empty())
{
char top = operators.top();
while (isoperator(top))
{
if (op[o1].first < op[top].first+offset)
{
postfix += top;
postfix += " ";
operators.pop();
}
else
break;
if (operators.empty())
break;
else
top = operators.top();
}
}
operators.push(o1);
iss >> tmp;
}
else if (token == '(')
{
operators.push(token);
iss >> tmp;
}
else if (token == ')')
{
while (operators.top() != '(')
{
postfix += operators.top();
postfix += " ";
operators.pop();
}
operators.pop();
iss >> tmp;
}
else iss.get(tmp);
}
while (!operators.empty()) {
postfix += operators.top();
postfix += " ";
operators.pop();
}
}Context
StackExchange Code Review Q#148452, answer score: 2
Revisions (0)
No revisions yet.