Shunting-yard algorithm for expression parser

Question

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.

• miscco: Is there a reason you do not use a range based loop in the second last loop?
• Chris: @miscco that was my bad. I forgot that you didn't have to implement a 'in' operator, for your custom classes.
• Yonlif: I think you are missing a while loop - read this code.
• user191336: @ChristianDean A beginner question: What should I substitute top() for when I use the standard linked list?
• Chris: 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.

Answer 1

• 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);
  

• Chris: 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.
• vnp: @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.
• Chris: 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.
• user191336: @vnp Just Curious, but what can I use in place of the top() function when using standard linked list?
• dgnuff: One comment on this. With only two precedence levels, this works as is. However, if you plan to extend it to three or more precedence levels, as I did when trying to produce a micro C parser, you should change if ((op_precedence[stack_top()] >= op_precedence[c])) to while ((op_precedence[stack_top()] >= op_precedence[c])) so it handles 1 + 2 * 3 & 4 correctly: you need to unwind both the * and the + on the stack before pushing the &. Other than that, this is one of the most clean and simple to understand implementations of Dijkstra's algorithm I've ever seen.