Last active
February 18, 2025 14:05
-
-
Save Mukundan314/79e98447a8478b8e34afe2256bbc048b to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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