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
118
119
120
121
122
123
124
125
126
127
128
129
|
/* rpn.c
*
* Takes a string of reverse polish notation math and pretty-prints it with
* parenthesis. Recognizes the {*, +, -, /} operators and ignores everything
* else.
*
*/
/*
- tree data structure
- read in integer function (std?)
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define LINE_LEN 1024
struct rpn_node {
char val;
struct rpn_node *left;
struct rpn_node *right;
};
int rpn_parse(char s[], struct rpn_node *node);
void rpn_print(struct rpn_node *node);
int rpn_eval(struct rpn_node *node);
int isoper(char c);
int main(void) {
char line[LINE_LEN] = "";
struct rpn_node root_node;
char tc;
int i,j;
// read string
fgets(line, LINE_LEN, stdin);
// reverse it
j = strlen(line) - 1;
for(i = 0; i <= j/2; i++) {
tc = line[i];
line[i] = line[j-i];
line[j-i] = tc;
}
// parse it down to single char numbers and opers
for(i = j = 0; i < strlen(line); i++) {
if(isdigit(line[i]) || isoper(line[i]))
line[j++] = line[i];
}
line[j] = '\0';
//printf("Compressed: %s\n", line);
// recursively parse down and store result in right; then recursively parse
// down and store result in left
rpn_parse(line, &root_node);
// spider down the tree to the left, printing
rpn_print(&root_node);
printf(" = %d\n", rpn_eval(&root_node));
return;
// &new_node = malloc(sizeof(struct node))
}
// returns the number of characters that got chomped up
int rpn_parse(char s[], struct rpn_node *node) {
int i=0;
node->val = s[0];
i++;
//printf("Got len=%d, isoper=%d: %s\n", (int)strlen(s), isoper(s[0]), s);
if(isoper(s[0])) {
//printf("Got an oper: %c\n", s[0]);
// load up right and left
node->right = malloc(sizeof(struct rpn_node));
node->left = malloc(sizeof(struct rpn_node));
i += rpn_parse(&s[i], node->right);
i += rpn_parse(&s[i], node->left);
}
return i;
}
void rpn_print(struct rpn_node *node) {
if(isoper(node->val)) {
printf("(");
rpn_print(node->left);
printf(" %c ", node->val);
rpn_print(node->right);
printf(")");
} else {
printf("%c", node->val);
}
}
int isoper(char c) {
switch(c) {
case '+':
case '-':
case '*':
case '/':
return 1;
break;
default:
return 0;
}
}
int rpn_eval(struct rpn_node *node) {
if(isdigit(node->val)) {
return node->val - '0';
}
switch(node->val) {
case '+':
return rpn_eval(node->left) + rpn_eval(node->right);
case '-':
return rpn_eval(node->left) - rpn_eval(node->right);
case '*':
return rpn_eval(node->left) * rpn_eval(node->right);
case '/':
return rpn_eval(node->left) / rpn_eval(node->right);
default:
printf("ERROR: unexpected character '%c'.", node->val);
exit(-1);
}
}
|
