mathshell/parser.cpp at master · hitensj/mathshell · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include "parser.h"
#include <stack>
#include <stdexcept>

int Parser::precedence(const std::string& op) const {
    if (op == "+" || op == "-") return 1;
    if (op == "*" || op == "/" || op == "%") return 2;
    if (op == "^") return 3;
    if (op == "u-") return 4;
    return 0;
}

bool Parser::isRightAssociative(const std::string& op) const {
    return op == "^";
}

std::vector<Token> Parser::toPostfix(const std::vector<Token>& tokens) {
    std::vector<Token> output;
    std::stack<Token> ops;

    for (const Token& tok : tokens) {
        switch (tok.type) {

        case TokenType::NUMBER:
        case TokenType::VARIABLE:
            output.push_back(tok);
            break;

        case TokenType::FUNCTION:
            ops.push(tok);
            break;

        case TokenType::OPERATOR: {
            while (!ops.empty()
                && ops.top().type == TokenType::OPERATOR
                && (precedence(ops.top().value) > precedence(tok.value)
                    || (precedence(ops.top().value) == precedence(tok.value)
                        && !isRightAssociative(tok.value))))
            {
                output.push_back(ops.top());
                ops.pop();
            }
            ops.push(tok);
            break;
        }

        case TokenType::LEFT_PAREN:
            ops.push(tok);
            break;

        case TokenType::RIGHT_PAREN: {
            while (!ops.empty() && ops.top().type != TokenType::LEFT_PAREN) {
                output.push_back(ops.top());
                ops.pop();
            }
            if (ops.empty())
                throw std::runtime_error("mismatched parentheses");
            ops.pop();

            if (!ops.empty() && ops.top().type == TokenType::FUNCTION) {
                output.push_back(ops.top());
                ops.pop();
            }
            break;
        }

        default:
            break;
        }
    }

    while (!ops.empty()) {
        if (ops.top().type == TokenType::LEFT_PAREN)
            throw std::runtime_error("mismatched parentheses");
        output.push_back(ops.top());
        ops.pop();
    }

    return output;
}