/* (c) Copyright 2007, Peter Goodman peter.goodman@gmail.com *//* goals: allow result from previous calculation to be able to be used in next calculation via the _ allow sub-expressions within brackets allow exponent operator perform all calculations in floating point */#include <stdlib.h>#include <stdio.h>#include "types.h"#include "calc.h"#include "operators.h"/* return a pointer to an expression node */Expr *new_expression() { Expr *node; if( (node = (Expr *)malloc( sizeof(Expr) )) == NULL) FATAL_ERROR("\nError: could not allocate space for expression " \ "node.\n"); /* defaults */ node->parent = NULL; node->left = NULL; node->right = NULL; node->op = NULL; return node;}/* return a pointer to a new stack frame, and push it onto the stack. */StackFrame *push_stack_frame(StackFrame *up) { StackFrame *frame; if( (frame = (StackFrame *)malloc( sizeof(StackFrame) )) == NULL) FATAL_ERROR("\nError: could not allocate space for a expression " \ "frame.\n"); /* defaults, required */ frame->up = up; frame->is_root = 0; frame->root = NULL; frame->curr_leaf = NULL; frame->curr_node = NULL; frame->down = NULL; if(up) up->down = frame; return frame;}/* pop the frame off the stack and return the root node of the expressions inside it to append onto the expressions in the parent stack. Note: Expr *root must be taken out beforehand. */StackFrame *pop_stack_frame(StackFrame *frame) { StackFrame *up = frame->up; if(frame->down != NULL) FATAL_ERROR("\nError: Frame being popped when child frame exists.\n"); /* break the reference to it */ if(frame->up != NULL) frame->up->down = NULL; /* remove all references */ frame->up = NULL; frame->root = NULL; frame->curr_leaf = NULL; frame->curr_node = NULL; frame->down = NULL; free(frame); frame = NULL; return up;}int is_num(char ch) { return ((ch >= '0' && ch <= '9') || ch == '.');}float post_order(Expr *node) { float result, left = 0.0, right = 0.0; if(node->op == NULL) { result = node->val; } else { if(node->left != NULL) left = post_order(node->left); if(node->right != NULL) right = post_order(node->right); result = (*(node->op))(left, right); } /* free up the allocated memory */ free(node); node = NULL; return result;}/* Place curr_node as one of the left/right children of curr_leaf, as long as one of those children is equal to def, which is usually a null pointer unless dealing with higher priority operators. */void place_on_leaf(Expr *curr_leaf, Expr *curr_node, Expr *def) { if(curr_leaf != NULL) { if(curr_leaf->left == def) curr_leaf->left = curr_node; else if(curr_leaf->right == def) curr_leaf->right = curr_node; else FATAL_ERROR("Error: could not place node on leaf.\n"); curr_node->parent = curr_leaf; }}/* Parse an expression */int parse_expression(struct Result *result) { /* the buffer holding the entire expression */ char buffer[MAX_LINE_LENGTH], ch; int char_count = 0, i = 0, j = 0, p; float value = 0; char num[16]; /* limit incoming numbers to 15 digits + \0 */ StackFrame *f; Expr *temp_root = NULL; /* get all the useful chars into a buffer, this is essentially a simplified lexer stage where I "tokenize", or rather restrict the inputs to the parser. */ /* !!! might get rid of this loop altogether */ do { ch = getchar(); /* quit the program */ if(ch == 'q') { return 0; } /* enter is pressed, break out of loop and parse expression */ if(ch == '\n') { break; } /* bring in a new character, make sure we get ones we want */ if( is_num(ch)|| \ ch == '*' || ch == '+' || ch == '/' || ch == '-' || \ ch == '^' || ch == '(' || ch == ')' || \ ch == '_' \ ) { buffer[char_count++] = ch; } } while(char_count < MAX_LINE_LENGTH); /* create the first stack frame */ f = push_stack_frame(NULL); f->is_root = 1; /* Parser stage, move the infix expressions into binary tree representation. */ for(; i < char_count; i++) { ch = buffer[i]; /* allocate our current node */ f->curr_node = new_expression(); if(is_num(ch) || ch == '_') { /* use the value of the previous calculation, zero by default */ if(ch == '_') { f->curr_node->val = result->curr; /* collect a number as a string, then convert it to a float */ } else { j = 0; p = 0; for(j = 0, p = 0; j < 15 && i < char_count && \ is_num(buffer[i]); i++, j++) { ch = buffer[i]; /* make sure a number has only one decimal in it */ if(ch == '.') { if(p >= 1) PARSE_ERROR("Parse Error: too many periods in "\ "number.\n"); p++; } num[j] = ch; } num[j] = '\0'; /* add null pointer to make sure we can treat this as a string for conversion. */ f->curr_node->val = atof(num); /* convert to float */ i--; /* make sure next loop we start from the right spot */ } f->curr_node->op = NULL; /* operand, not operator */ /* place this node */ if(f->root == NULL) f->root = f->curr_node; else place_on_leaf(f->curr_leaf, f->curr_node, NULL); /* operator encountered */ } else { /* error, can't start with an operator */ if(f->root == NULL && ch != '(') { PARSE_ERROR("Parse Error: expressions may only begin with " \ "a number or a (.\n"); } /* supported operators */ switch(ch) { case '(': /* curr stack frame */ free(f->curr_node); /* don't need it, it's the ( */ f->curr_node = NULL; /* don't let it hang */ /* child stack frame */ f = push_stack_frame(f); break; case ')': /* curr stack frame */ free(f->curr_node); /* don't need it, it's the ) */ f->curr_node = NULL; /* don't let it hang for when the recursive function goes over. */ temp_root = f->root; if(f->is_root) PARSE_ERROR("Parse Error: Too many closing braces " \ "in expression."); /* parent frame */ f = pop_stack_frame(f); /* parent frame has no root, lets just move the temp root up then. */ if(f->root == NULL) { f->root = temp_root; } else { if(temp_root != NULL) { place_on_leaf(f->curr_leaf, temp_root, NULL); f->curr_node = temp_root; temp_root = NULL; /* don't need this anymore */ } } break; /* curr_node becomes curr_leaf. Everything that was curr_leaf becomes the left value of curr_node. */ case '^': case '*': case '/': /* change the parenting order */ if(f->curr_leaf == f->root) f->root = f->curr_node; f->curr_node->parent = f->curr_leaf->parent; place_on_leaf(f->curr_leaf->parent, f->curr_node, \ f->curr_leaf); f->curr_leaf->parent = f->curr_node; f->curr_node->left = f->curr_leaf; /*f->curr_node->op = ch;*/ break; /* make curr_node the new root. */ case '+': case '-': f->root->parent = f->curr_node; f->curr_node->right = f->root; f->root = f->curr_node; /*f->curr_node->op = ch;*/ break; } /* a bit redundant.. needs rethinking! */ switch(ch) { case '^': f->curr_node->op = &op_exponent; break; case '*': f->curr_node->op = &op_multiply; break; case '/': f->curr_node->op = &op_divide; break; case '+': f->curr_node->op = &op_add; break; case '-': f->curr_node->op = &op_subtract; break; } } f->curr_leaf = f->curr_node; } /* Interpreter stage, recursively walk the tree, postorder, and interpret the expressions to come to a final result. */ /* assign the result */ result->prev = result->curr; result->curr = post_order(f->root); return 1;}/* run the program */int main() { struct Result result = {0.0, 0.0}; printf("\nWelcome to Peter's awesome calculator.\n"); printf("Type 'q' and press enter to quit the calculator at any time\n"); while( (printf("\n>>> "), parse_expression(&result)) ) { printf("= %f\n", result.curr); } printf("Goodbye.\n"); return 0;}