#include <stdio.h>
#include <stdlib.h>
struct Node {
enum { VAR, INT, OP } type;
union {
char var;
int value;
struct {
char op;
Node *left;
Node *right;
} node;
};
};
typedef const char *string;
Node *expr(string& str);
// factor = n | d | (expr).
Node *factor(string& str) {
if ('0' <= *str && *str <= '9') {
Node *digit = new Node;
digit->type = Node::INT;
digit->value = *str - '0';
++str;
return digit;
} else if ('a' <= *str && *str <= 'z') {
Node *var = new Node;
var->type = Node::VAR;
var->var = *str;
++str;
return var;
} else if (*str == '(') {
++str;
Node *subexpr = expr(str);
if (*str != ')') {
printf("unbalanced bracket\n");
exit(1);
}
++str;
return subexpr;
} else {
printf("unknown symbol %c\n", *str);
exit(1);
}
}
// term = factor { (*|/) factor }.
Node *term(string& str) {
Node *res = factor(str);
while (*str == '*' || *str == '/') {
Node *mul = new Node;
mul->type = Node::OP;
mul->node.op = *str;
mul->node.left = res;
++str;
mul->node.right = factor(str);
res = mul;
}
return res;
}
// expr = term { (+|-) term }.
Node *expr(string& str) {
Node *res = term(str);
while (*str == '+' || *str == '-') {
Node *summ = new Node;
summ->type = Node::OP;
summ->node.op = *str;
summ->node.left = res;
++str;
summ->node.right = term(str);
res = summ;
}
return res;
}
void indent(int n) {
for(int i = 0; i < n; ++i) {
printf(" ");
}
}
void print_tree(Node *node, int depth) {
switch (node->type) {
case Node::VAR:
indent(depth);
printf("variable %c\n", node->var);
break;
case Node::INT:
indent(depth);
printf("value %d\n", node->value);
break;
case Node::OP:
indent(depth);
printf("Node %c {\n", node->node.op);
print_tree(node->node.left, depth + 1);
print_tree(node->node.right, depth + 1);
indent(depth);
printf("}\n");
break;
}
}
int main(int argc, char *argv[]) {
if (argc < 2) {
printf("bad parameter\n");
return 1;
}
const char *input = argv[1];
Node *n = expr(input);
print_tree(n, 0);
return 0;
}