# Shunting-yard algorithm for expression parser

After reading about the Shunting-yard algorithm, I decided to try to make a expression parser, before trying to make a actual language parser, using it. The way i translated the algorithm into C++ code seems pretty compact, so there is really not much code to post:

## Shunting-yard algorithm(in C++):

#include <iostream>
#include <string>
#include<vector>
#include<map>
#include "list.h"

bool isInteger(char &c) {
return (c >= '0') && (c <= '9');
}

int main() {
std::vector<char> output;
List<char> stack;
List<char>::iterator it = stack.begin();

std::string expr("2-2*3/6");
std::map<char, int> op_precedence;
op_precedence['+'] = 10;
op_precedence['-'] = 10;
op_precedence['*'] = 20;
op_precedence['/'] = 20;

for (char &c : expr) {
if (isInteger(c)) {
output.push_back(c);
} else {
if ((stack.size() > 0)) {
if ((op_precedence[stack.top()] >= op_precedence[c])) {
output.push_back(stack.top());
stack.pop();
stack.push(c);
} else if ((op_precedence[stack.top()] < op_precedence[c])) {
stack.push(c);
}
} else {
stack.push(c);
}
}
}
for (it = stack.begin(); it != stack.end(); it++) {
output.push_back(*it);
}

for (auto &i : output) {
std::cout << i << ' ';
}

return 0;
}


The only thing I should note, is that the list.h I include, is not part of the standard library. That is a linked list class I finished up a few hours ago. If the code for the linked list is really necessary, I'll post it, but I don't think it will. I pretty much behaves like a normal linked list. In fact, you could exchange it with the standard linked list. Just replace pop() with pop_front(), push() with push_back(), and stack.top() with stack.front().

I also should mention that I have not included parenthesis yet, as I'm just trying to get the basics down first.

• Is there a reason you do not use a range based loop in the second last loop? – miscco Sep 15 '16 at 7:09
• @miscco that was my bad. I forgot that you didn't have to implement a 'in' operator, for your custom classes. – Christian Dean Sep 15 '16 at 7:44
• I think you are missing a while loop - read this code. – Yonlif Dec 20 '18 at 9:04
• @ChristianDean A beginner question: What should I substitute top() for when I use the standard linked list? – Khushraj Rathod Jan 28 '19 at 6:43
• Hey @Holyprogrammer sorry for the very late reply. To answer your question, assuming you are using the standard linked list class like a stack, list::front should give you want. The "top" (i.e. first element) of the linked list. – Christian Dean Jan 30 '19 at 5:21

• isInteger is not needed. Use std::isdigit.

• Trust the logic. An else if condition is mutually exclusive with if condition. There is no need to test for it - you already know it is true. A simple else is enough. But see also the next point.

• Notice that all code paths in the else clause necessarily push(c). Factor it out:

if ((stack.size() > 0) {
if ((op_precedence[stack_top()] >= op_precedence[c])) {
output.push_back(stack.top());
stack.pop();
}
}
stack.push(c);

• Excellent answer vnp, thank you. But if I was going to use string's instead of char's, wouldn't I have to make a my own isdigit() function? Or is there a standard library function for that too. – Christian Dean Sep 15 '16 at 17:26
• @Mr.goosberry Unless I misread the question, the best way to parse an integer from the string is to call strtol or something in its family, and analyze the end pointer. – vnp Sep 15 '16 at 17:39
• Oh no. In my question I am working with characters. your answer is in the correct context. I was asking if I would have to make my own function to test if a string is an integer. Or if there is some standard library function for already. I'll check out strtol though. Thanks. – Christian Dean Sep 15 '16 at 17:49
• @vnp Just Curious, but what can I use in place of the top() function when using standard linked list? – Khushraj Rathod Jan 28 '19 at 6:53