Skip to content

Instantly share code, notes, and snippets.

@Mukundan314
Last active February 18, 2025 14:05
Show Gist options
  • Save Mukundan314/79e98447a8478b8e34afe2256bbc048b to your computer and use it in GitHub Desktop.
Save Mukundan314/79e98447a8478b8e34afe2256bbc048b to your computer and use it in GitHub Desktop.
#include <iostream>
#include <queue>
#include <stack>
#include <string>
enum TokenType {
NUMBER,
LBRAC,
RBRAC,
PLUS,
MINUS,
MUL,
DIV,
POW,
};
struct Token {
TokenType type;
std::string value;
};
struct Node {
std::string op;
Node *left, *right;
void print(int indent = 0) {
for (int i = 0; i < indent; i++)
std::cout << ' ';
std::cout << op << std::endl;
if (left != nullptr)
left->print(indent + 4);
if (right != nullptr)
right->print(indent + 4);
}
};
Node *parse_num(std::queue<Token> &);
Node *parse_brac(std::queue<Token> &);
Node *parse_mul(std::queue<Token> &);
Node *parse_div(std::queue<Token> &);
Node *parse_minus(std::queue<Token> &);
Node *parse_plus(std::queue<Token> &);
Node *parse(std::queue<Token> &);
Node *parse_num(std::queue<Token> &tokens) {
// possibily parse unary operators here
if (!tokens.size() || tokens.front().type != NUMBER)
throw;
auto token = tokens.front();
tokens.pop();
return new Node{token.value, nullptr, nullptr}; // yeah somewhat weird that I'm putting the number in the op
}
Node *parse_brac(std::queue<Token> &tokens) {
if (tokens.size() && tokens.front().type == LBRAC) {
tokens.pop();
auto ret = parse(tokens);
if (!tokens.size() || tokens.front().type != RBRAC)
throw;
tokens.pop();
return ret;
}
return parse_num(tokens);
}
Node *parse_pow(std::queue<Token> &tokens) {
std::stack<Node *> st;
st.push(parse_brac(tokens));
while (tokens.size() && tokens.front().type == POW) {
tokens.pop();
st.push(parse_brac(tokens));
}
auto ret = st.top();
for (st.pop(); st.size(); st.pop())
ret = new Node{"^", st.top(), ret};
return ret;
}
Node *parse_mul(std::queue<Token> &tokens) {
auto ret = parse_pow(tokens);
while (tokens.size() && tokens.front().type == MUL) {
tokens.pop();
ret = new Node{"*", ret, parse_pow(tokens)};
}
return ret;
}
Node *parse_div(std::queue<Token> &tokens) {
auto ret = parse_mul(tokens);
while (tokens.size() && tokens.front().type == DIV) {
tokens.pop();
ret = new Node{"/", ret, parse_mul(tokens)};
}
return ret;
}
Node *parse_minus(std::queue<Token> &tokens) {
auto ret = parse_div(tokens);
while (tokens.size() && tokens.front().type == MINUS) {
tokens.pop();
ret = new Node{"-", ret, parse_div(tokens)};
}
return ret;
}
Node *parse_plus(std::queue<Token> &tokens) {
auto ret = parse_minus(tokens);
while (tokens.size() && tokens.front().type == PLUS) {
tokens.pop();
ret = new Node{"+", ret, parse_minus(tokens)};
}
return ret;
}
Node *parse(std::queue<Token> &tokens) { return parse_plus(tokens); }
std::queue<Token> lex(std::string expr) {
std::queue<Token> tokens;
int i = 0;
while (i < expr.size()) {
if (isspace(expr[i])) {
i++;
} else if (expr[i] == '+') {
tokens.push(Token{PLUS, "+"});
i++;
} else if (expr[i] == '-') {
tokens.push(Token{MINUS, "-"});
i++;
} else if (expr[i] == '*') {
tokens.push(Token{MUL, "*"});
i++;
} else if (expr[i] == '/') {
tokens.push(Token{DIV, "/"});
i++;
} else if (expr[i] == '^') {
tokens.push(Token{POW, "^"});
i++;
} else if (expr[i] == '(') {
tokens.push(Token{LBRAC, "("});
i++;
} else if (expr[i] == ')') {
tokens.push(Token{RBRAC, ")"});
i++;
} else if (isdigit(expr[i])) {
std::string num;
for (; i < expr.size() && isdigit(expr[i]); i++)
num.push_back(expr[i]);
tokens.push(Token{NUMBER, num});
} else {
throw;
}
}
return tokens;
}
int main() {
auto tokens = lex("5 - 2 - 3 * 10 + (1 - 2 + 3)^2^3^5 * 5 / 100 + 2");
Node *node = parse(tokens);
node->print();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment