Простой рекурсивный спуск

  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
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#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;
}