User Documentation | System Documentation | C code
Purpose:
This program takes in expressions as command line parameters, creates the binary
expression tree using pointers, and then uses recursion to evaluate the tree.
All information is supplied on a single command line. Operators must be in post
fix format. The program accepts command line arguments and acts upon them. They
user can choose the following math operations, +,-,Ó*Ó,/. Note multiply *-must
be in quotes. Usage: The command line is entered as follows: be_tree operand
operand operator . . . operator can be +, -, *, / some sample calls would be:
be_tree 4 5 + 47 3.44 / Ò*Ó be_tree 4 5 + 24.34 0.001 / Ò*Ó 1 5 / 5 654 - Ò*Ó
/
Format of Inputs:
Only command line inputs are allowed. Operators must be post fix. Two operands
must be given, or the result of an operation.
For example: 8 3 + 2 3 + Ò*Ó -the multiplication receives as operands the results
of 8 + 3 and 2 + 3.
Sample Inputs:
enterprise% be_tree 4 5 + 24.34 0.001 / Ò*Ó 1 5 / 5 654 - Ò*Ó /
Expression 4 5 + 24.34 0.001 / * 1 5 / 5 654 - * / evaluates to -1687.67
enterprise% be_tree 12 45 / 0.215 .4433 - "*"
Segmentation Fault (core dumped)
the above command failed because numbers less than one must be preceded by a
zero; 0.122
enterprise% be_tree 12 45 / 0.215 0.4433 - "*"
Expression 12 45 / 0.215 0.4433 - *evaluates to -0.06
enterprise% be_tree 22 3 -
Expression 22 3 - evaluates to 19.00
enterprise% be_tree 1 9 -
Expression 1 9 - evaluates to -8.00
enterprise% be_tree 54646848 321322 "*"
Expression 54646848 321322 * evaluates to 17559234543616.00
enterprise% be_tree 3 4 / Expression 3 4 /
evaluates to 0.75
Purpose:
This program takes in expressions as command line parameters, creates the binary
expression tree using pointers, and then uses recursion to evaluate the tree.
All information is supplied on a single command line. Operators must be in post
fix format. The program accepts command line arguments and acts upon them. They
user can choose the following math operations, +,-,Ó*Ó,/. Note multiply *-must
be in quotes.
Author:
John Lynch
Class:
CS 342-60
Known Problems:
prefix operators such as -2, cannot be used. Numbers less than 1 must be preceded
by a 0; 0.123. Development Environment: The code was written in BB Edit on the
MacOS. It was test compiled in Metrowerks Codewarrior. It was finally compiled
using cc on the Sun workstation Enterprise.
Target Environment:
Same
Design Documentation:
Design method was stepwise refinement with modularity .
All functions are contained in be_tree.c: Typedefs and function prototypes are
contained in the header file be_tree.h
function create_tree
Purpose: Creates a TreeNodeType (structure), initializes left and right fields
to NULL Returns the address of the node to the caller
function build_tree
Purpose: Recursive function, builds a binary tree from parameters passed to
it Base case is when argvÕs argument is a number.
Preconditions: receives the address of an integer used is decrementing through
argv and array argv (an array of pointers to type char)
function print_tree
Purpose: Recursive function,prints a binary tree from parameters passed to it.
Base case is when pointer passed to it is NULL
Preconditions: receives the address of an TreeTypeNode (structure)
function evaluate_tree
Purpose: Recursive function, operates on numerical values in tree. Operation
depends on what operators are in tree. Evaluation is postfix
Post Conditions: Returns final value to caller. How to Build To compile on UNIX:
cc -o be_tree be_tree.c note:be_tree.h must be in the same directory.
How to Build
To compile on UNIX: cc -o be_tree be_tree.c note:be_tree.h must be in the same
directory.
/****************************************************************************************/
/* */
/* Program Name: be_tree.c */
/* Language: C */
/* Purpose: takes in expressions as command line parameters, creates a binary */
/* expression tree using pointers, and uses recursion to evaluate the tree. */
/* */
/* Usage: execute with command line arguments. For example be_tree 3 4 + 2 3 - * */
/* */
/* Restrictions: No prefix operators (for example -2) are allowed. */
/* every operand must have two operators, or the result of an operation */
/* */
/* Environment: be_tree.h must be present in the directory that be_tree.c is in. */
/* */
/* Author: John Lynch */
/* */
/* */
/****************************************************************************************/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <type.h>
#include "be_tree.h"
/*Preconditions: argc contains number of arguments to program */
/* argv s an array of size argc+1 pointers to arguments. */
/* Last pointer is NULL */
int main(int argc, char *argv[]){
TreeType root=NULL;
int counter, i;
float answer;
counter=argc-1;
if(argc<=1){
printf("\n\nPlease supply command line arguments\n\n");
}else{
root=build_tree(&counter, argv);
/*print_tree(root); call used for testing*/
answer=evaluate_tree(root);/*gets final result from evaluate_tree*/
printf("\nExpression ");
for(i=1;i0){
if(isdigit(argv[*element_num][0])){
tempnode=create_tree();
(*tempnode).right=NULL;
(*tempnode).left=NULL;
(*tempnode).data=(argv[count]);
*element_num =count-1;
}
else{
tempnode=create_tree();
(*tempnode).data=argv[count];
*element_num =count-1;
(*tempnode).right=build_tree(element_num, argv);
(*tempnode).left=build_tree(element_num, argv);
}/*if*/
return(tempnode);
}/*while*/
}/*build_tree*/
/***************function print_tree******************************************************/
/* Purpose: Recursive function,prints a binary tree from parameters passed to it */
/* Base case is when pointer passed to it is NULL */
/* Preconditions: receives the address of an TreeTypeNode (structure) */
/* */
/* Post Conditions: none */
/* */
/* Side effects: none */
/* comments: This function is used in this program as a test to see if the tree is */
/* built correctly */
/****************************************************************************************/
void print_tree(TreeType root){
if (root==NULL){
/*do nothing*/
}else{
print_tree((*root).left);
print_tree((*root).right);
printf("%s\n",(*root).data);
}/*if*/
return;
}/*print_tree*/
/***************function evaluate_tree***************************************************/
/* Purpose: Recursive function, operates on numerical values in tree. Operation depends */
/* on what operators are in tree. Evaluation is postfix */
/* */
/* Post Conditions: Returns final value to caller. */
/* */
/* Side effects: none */
/****************************************************************************************/
float evaluate_tree(TreeType temp_ptr){
float value,lvalue, rvalue;
char c;
char *temp_value;
temp_value=(*temp_ptr).data;
c=temp_value[0];
if(isdigit(c)){
value=(atof(temp_value));
}else{
lvalue=evaluate_tree((*temp_ptr).left);
rvalue=evaluate_tree((*temp_ptr).right);
c=(*temp_ptr).data[0];
switch (c)
{
case '+':
value=lvalue+rvalue;
break;
case '-':
value=lvalue-rvalue;
break;
case '*':
value=lvalue*rvalue;
break;
case '/' :
if(rvalue!=0){
value=lvalue/rvalue;
}else{
printf("\n\nDivide by zero not allowed");
value=0;
}/*if-else*/
break;
default:
printf("\n\nUnknown operator");
value=0;
break;
}/*switch*/
}/*if-else*/
return(value);
}/*evaluate_tree*/
/*end file*/