4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Is there a reason you do not use a range based loop in the second last loop? \$\endgroup\$ – miscco Sep 15 '16 at 7:09
  • \$\begingroup\$ @miscco that was my bad. I forgot that you didn't have to implement a 'in' operator, for your custom classes. \$\endgroup\$ – Christian Dean Sep 15 '16 at 7:44
  • \$\begingroup\$ I think you are missing a while loop - read this code. \$\endgroup\$ – Yonlif Dec 20 '18 at 9:04
  • \$\begingroup\$ @ChristianDean A beginner question: What should I substitute top() for when I use the standard linked list? \$\endgroup\$ – Holyprogrammer Jan 28 at 6:43
  • \$\begingroup\$ 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. \$\endgroup\$ – Christian Dean Jan 30 at 5:21
6
\$\begingroup\$
  • 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);
    
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Christian Dean Sep 15 '16 at 17:26
  • \$\begingroup\$ @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. \$\endgroup\$ – vnp Sep 15 '16 at 17:39
  • \$\begingroup\$ 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. \$\endgroup\$ – Christian Dean Sep 15 '16 at 17:49
  • \$\begingroup\$ @vnp Just Curious, but what can I use in place of the top() function when using standard linked list? \$\endgroup\$ – Holyprogrammer Jan 28 at 6:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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