1 /*
2 * Copyright (C) 2015 Texas Instruments Inc
3 *
4 * Aneesh V <aneesh@ti.com>
5 *
6 * Licensed under the Apache License, Version 2.0 (the "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18 #include "bqt.h"
19 #include <stdio.h>
20 #include <string.h>
21 #include <stdint.h>
22 #include <ctype.h>
23 #include <math.h>
25 enum op_type_t {
26 INVALID_OPERATOR = 0,
27 OPERATOR_EXPONENT,
28 OPERATOR_MULT,
29 OPERATOR_DIV,
30 OPERATOR_ADD,
31 OPERATOR_SUBTRACT,
32 };
34 enum op_precedence_t {
35 OP_PREC_EXPONENT = 6,
36 OP_PREC_MULT_DIV = 5,
37 OP_PREC_ADD_SUB = 4,
39 };
41 enum op_assoc_t {
42 LEFT_ASSOCIATIVE,
43 RIGHT_ASSOCIATIVE,
44 };
46 /*
47 * Not supporting multi-character operators as of now.
48 * Not used in any bqz files I have seen and it doesn't
49 * look like bqStudio supports any operators other than
50 * the basic ones. So, no need to complicate things by
51 * supporting the full array of C operators.
52 */
53 struct operator_t {
54 char op_char;
55 enum op_type_t op_num;
56 enum op_precedence_t prec;
57 enum op_assoc_t assoc;
58 double (*fp)(double op1, double op2);
59 };
61 static double mult(double op1, double op2)
62 {
63 return op1 * op2;
64 }
66 static double my_div(double op1, double op2)
67 {
68 return op1 / op2;
69 }
71 static double add(double op1, double op2)
72 {
73 return op1 + op2;
74 }
76 static double sub(double op1, double op2)
77 {
78 return op1 - op2;
79 }
81 static double my_pow(double op1, double op2)
82 {
83 return pow(op1, op2);
84 }
86 const struct operator_t operators[] = {
87 {'^', OPERATOR_EXPONENT, OP_PREC_EXPONENT, RIGHT_ASSOCIATIVE, my_pow},
88 {'*', OPERATOR_MULT, OP_PREC_MULT_DIV, LEFT_ASSOCIATIVE, mult},
89 {'/', OPERATOR_DIV, OP_PREC_MULT_DIV, LEFT_ASSOCIATIVE, my_div},
90 {'+', OPERATOR_ADD, OP_PREC_ADD_SUB, LEFT_ASSOCIATIVE, add},
91 {'-', OPERATOR_SUBTRACT, OP_PREC_ADD_SUB, LEFT_ASSOCIATIVE, sub},
92 };
94 enum tok_type_t {
95 OPERATOR,
96 LEFT_PARENTHESIS,
97 RIGHT_PARENTHESIS,
98 OPERAND_CONST,
99 OPERAND_X,
100 };
103 struct token_t {
104 double val;
105 enum tok_type_t type;
106 const struct operator_t *op;
107 };
109 struct queue_t *create_queue()
110 {
111 struct queue_t *q = (struct queue_t *) malloc(sizeof(struct queue_t));
113 q->head = NULL;
114 q->tail = NULL;
115 q->curr = NULL;
117 return q;
118 }
120 void delete_queue(struct queue_t *q)
121 {
122 struct node_t *node = q->head;
123 struct node_t *next;
125 while (node) {
126 next = node->next;
127 free(node->val_p);
128 free(node);
129 node = next;
130 }
132 free(q);
133 }
136 static void push_front(struct queue_t *q, void *val_p)
137 {
138 struct node_t *node = (struct node_t *) malloc(sizeof(struct node_t));
140 node->val_p = val_p;
141 if (q->head)
142 q->head->prev = node;
143 node->next = q->head;
144 node->prev = NULL;
145 q->head = node;
146 if (!q->tail)
147 q->tail = node;
148 }
150 static void push_back(struct queue_t *q, void *val_p)
151 {
152 struct node_t *node = (struct node_t *) malloc(sizeof(struct node_t));
154 node->val_p = val_p;
155 node->next = NULL;
156 if (q->tail)
157 q->tail->next = node;
158 node->prev = q->tail;
159 q->tail = node;
160 if (!q->head)
161 q->head = node;
162 }
164 static void* pop_front(struct queue_t* q)
165 {
166 if (!q->head)
167 return NULL;
169 struct node_t *front = q->head;
170 struct node_t *next = q->head->next;
172 void *val_p = front->val_p;
173 q->head = next;
174 if (next)
175 next->prev = NULL;
177 free(front);
179 return val_p;
180 }
182 static void reset_iterator(struct queue_t* q)
183 {
184 q->curr = q->head;
185 }
187 static void *get_next(struct queue_t *q)
188 {
189 if (!q->curr)
190 return NULL;
192 void *val_p = q->curr->val_p;;
194 q->curr = q->curr->next;
196 return val_p;
197 }
199 static void *front(struct queue_t* q)
200 {
201 if (q->head)
202 return q->head->val_p;
203 else
204 return NULL;
205 }
207 #if 0
208 static void *back(struct queue_t* q)
209 {
210 if (q->tail)
211 return q->tail->val_p;
212 else
213 return NULL;
214 }
215 #endif
217 static int get_operator(const char c, struct token_t *tok)
218 {
219 unsigned int i;
221 for (i = 0; i < sizeof(operators)/sizeof(operators[0]); i++) {
222 if (operators[i].op_char == c) {
223 tok->op = &operators[i];
224 return operators[i].op_num;
225 }
226 }
228 tok->op = NULL;
230 return INVALID_OPERATOR;
231 }
233 struct token_t *get_expr_token(const char *expr, const char **endptr)
234 {
235 if (!expr || !(*expr))
236 return NULL;
238 struct token_t tok;
239 char c = *expr;
240 char *tmp;
242 /* */
243 tmp = (char *) expr + 1;
245 if(isdigit(c)) {
246 //d = strtod(expr, &tmp);
247 tok.val = strtod(expr, &tmp);
248 if (expr == tmp) {
249 pr_err("Not a valid number at :%s\n", expr);
250 goto error;
251 }
252 tok.type = OPERAND_CONST;
253 } else if (c == 'x' || c == 'X') {
254 tok.type = OPERAND_X;
255 } else if (c == '(') {
256 tok.type = LEFT_PARENTHESIS;
257 } else if (c == ')') {
258 tok.type = RIGHT_PARENTHESIS;
259 } else {
260 if (get_operator(c, &tok) == INVALID_OPERATOR) {
261 pr_err("Not a valid token at :%s\n", expr);
262 goto error;
263 }
264 tok.type = OPERATOR;
265 }
267 struct token_t *ret_tok = (struct token_t *) malloc(sizeof(struct token_t));
268 if (ret_tok) {
269 *ret_tok = tok;
270 *endptr = tmp;
271 }
273 return ret_tok;
275 error:
276 *endptr = expr;
277 return NULL;
278 }
280 /*
281 Logic:
282 - Read a token.
283 - If the token is a number, then add it to the output queue.
284 - If the token is an operator, o1, then:
285 . while there is an operator token, o2, at the top of the operator stack, and either
286 o1 is left-associative and its precedence is less than or equal to that of o2, or
287 o1 is right associative, and has precedence less than that of o2,
288 . then pop o2 off the operator stack, onto the output queue;
289 . push o1 onto the operator stack.
290 - If the token is a left parenthesis (i.e. "("), then push it onto the stack.
291 - If the token is a right parenthesis (i.e. ")"):
292 . Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
293 . Pop the left parenthesis from the stack, but not onto the output queue.
294 . If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.
295 - When there are no more tokens to read:
296 . While there are still operator tokens in the stack:
297 If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses.
298 Pop the operator onto the output queue.
299 - Exit.
300 */
301 struct queue_t *parse_expression(const char *expr)
302 {
303 struct queue_t *outq = create_queue();
304 struct queue_t *op_stack = create_queue();
305 struct token_t *tok, *tmp_tok;
307 while ((tok = get_expr_token(expr, &expr))) {
308 switch(tok->type) {
309 case OPERAND_CONST:
310 case OPERAND_X:
311 push_back(outq, tok);
312 break;
313 case OPERATOR:
314 while ((tmp_tok = (struct token_t *) front(op_stack))) {
315 if ((tok->op->assoc == LEFT_ASSOCIATIVE && tok->op->prec <= tmp_tok->op->prec) ||
316 (tok->op->assoc == RIGHT_ASSOCIATIVE && tok->op->prec < tmp_tok->op->prec)) {
317 push_back(outq, tmp_tok);
318 pop_front(op_stack);
319 } else {
320 break;
321 }
322 }
323 push_front(op_stack, tok);
324 //push_front(op_stack, tok);
325 break;
326 case LEFT_PARENTHESIS:
327 push_front(op_stack, tok);
328 break;
329 case RIGHT_PARENTHESIS:
330 while ((tmp_tok = (struct token_t *) pop_front(op_stack)) &&
331 (tmp_tok->type != LEFT_PARENTHESIS)) {
332 push_back(outq, tmp_tok);
333 }
334 free(tok);
335 if (tmp_tok) {
336 /* Left parenthesis, we don't need it anymore either */
337 free(tmp_tok);
338 } else {
339 pr_err("Unmatched parenthesis, no left parenthesis matching right parenthesis at:%s\n", expr - 1);
340 goto error;
341 }
342 break;
343 default:
344 pr_err("Unexpected token just before :%s", expr);
345 goto error;
346 break;
347 }
348 }
350 /* End of stream, pop out the remaining opertors from operator stack */
351 while ((tmp_tok = (struct token_t *) pop_front(op_stack)) &&
352 (tmp_tok->type != LEFT_PARENTHESIS)) {
353 push_back(outq, tmp_tok);
354 }
356 if (tmp_tok) {
357 pr_err("Unmatched parenthesis, unmatched left parenthesis\n");
358 goto error;
359 }
361 delete_queue(op_stack);
362 return outq;
364 error:
365 delete_queue(op_stack);
366 delete_queue(outq);
367 pr_err("Parsing failed!\n");
368 return NULL;
369 }
371 /*
372 * Evaluate reverse polish notation expression:
373 * rpn_q - Expression in Reverse Polish(postfix) notation
374 * Logic: https://en.wikipedia.org/wiki/Reverse_Polish_notation#Postfix_algorithm
375 * limited to binary operators
376 */
377 double evaluate_expr(struct queue_t *rpn_q, double val)
378 {
379 double result;
380 struct token_t *tok, *tok_tmp, *opnd1, *opnd2;
381 struct queue_t *opnd_stack = create_queue();
383 reset_iterator(rpn_q);
384 while((tok = (struct token_t *) get_next(rpn_q))) {
385 switch(tok->type) {
386 case OPERAND_CONST:
387 case OPERAND_X:
388 tok_tmp = (struct token_t *) malloc(sizeof(struct token_t));
389 *tok_tmp = *tok;
390 if (tok->type == OPERAND_X)
391 tok_tmp->val = val;
392 push_front(opnd_stack, tok_tmp);
393 break;
394 case OPERATOR:
395 opnd2 = (struct token_t *) pop_front(opnd_stack);
396 opnd1 = (struct token_t *) front(opnd_stack);
397 if (!opnd1 || !opnd2) {
398 pr_err("Not enough operands for operator :%c\n", tok->op->op_char)
399 return 0;
400 }
401 opnd1->val = tok->op->fp(opnd1->val, opnd2->val);
402 free(opnd2);
403 break;
404 default:
405 break;
406 }
407 }
409 reset_iterator(opnd_stack);
410 opnd1 = (struct token_t *) get_next(opnd_stack);
411 opnd2 = (struct token_t *) get_next(opnd_stack);
412 result = opnd1->val;
413 delete_queue(opnd_stack);
414 if (opnd2) {
415 pr_err("More than one operand remaining in the stack, but no more operators remainig\n");
416 return 0;
417 }
419 return result;
420 }