up vote 3 down vote favorite

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(), and push() with push_back().

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

share|improve this question
    
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. – algerbrex Sep 15 '16 at 7:44
up vote 6 down vote accepted

  • 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);
share|improve this answer
    
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. – algerbrex 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. – algerbrex Sep 15 '16 at 17:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.