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.

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