8
\$\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\$
6
  • \$\begingroup\$ Is there a reason you do not use a range based loop in the second last loop? \$\endgroup\$
    – miscco
    Sep 15, 2016 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\$
    – Chris
    Sep 15, 2016 at 7:44
  • \$\begingroup\$ I think you are missing a while loop - read this code. \$\endgroup\$
    – Yonlif
    Dec 20, 2018 at 9:04
  • \$\begingroup\$ @ChristianDean A beginner question: What should I substitute top() for when I use the standard linked list? \$\endgroup\$
    – user191336
    Jan 28, 2019 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\$
    – Chris
    Jan 30, 2019 at 5:21

1 Answer 1

9
\$\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\$
5
  • \$\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\$
    – Chris
    Sep 15, 2016 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, 2016 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\$
    – Chris
    Sep 15, 2016 at 17:49
  • \$\begingroup\$ @vnp Just Curious, but what can I use in place of the top() function when using standard linked list? \$\endgroup\$
    – user191336
    Jan 28, 2019 at 6:53
  • \$\begingroup\$ 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. \$\endgroup\$
    – dgnuff
    Apr 26, 2020 at 3:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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