Implemeting an Open Addressing Hash Tables and reading data from a file Parsers using C
Posted on 2003-03-20
I am working on something right now and I Need an idea on how to start it.
Here is the scenrio
This programming projectis to write a simple expression parser The parser program repeatedly asks the user for an arithmetic expression and outputs its value. To make things a bit more interesting, the expressions may contain variables and functions.
As it runs, the program prompts the user for an assignment. The user might input
foo = 450*(bar/baz)
where bar and baz are variables defined in previous assignments. The program will first evaluate the expression in the right side of the assignment, and assign the result to the variable on the left side. The variable foo has now been defined and may appear in future expressions.
The expressions may consist of numbers (which may be integers or decimal numbers), previously defined variables and functions. A function consists of a function name immediately followed by the list of parameters in parentheses. The parser must recognize and evaluate the functions sin, cos, abs and max, where the first three functions take a single parameter, and the max function takes arbitrary many parameters, separated by commas.
For example, some assignments given to the parser might be
x = 1*2*3*4*5-5*-4*-3*-2*-1
y = 1.11 + 2.22 + -3.33 * 4.4444444
z = max(x,y,x*y,x+y,x/y)
quitealongvariablename = sin(cos(sin(cos(2))))
For these assignments, the program should output 0, -11.47, 0 and 0.7952, respectively. (The accuracy of your program may differ from these depending on how many decimals you choose to output.)
For simplicity, the program may assume that all expressions given to it are syntactically correct, so there is no need to implement error handling or error recovery in your parser. Also the expressions are guaranteed to contain only previously defined variables. Other rules for this project are:
The parser may do all the computations using the double type. There is no need to specifically handle overflows and numerical inaccuracy errors.
The input can be trusted to be a syntactically correct expression. However, it might contain spaces wherever they are allowed.
Multiplication is always used explicitly. For example, the expression x(y+z) would be syntactically incorrect, and is given in full as x*(y+z).
The parser should give multiplication and division operations a higher precedence than addition and subtraction. The associativity of the same-precedence operations may be arbitrary, though. (Especially both addition and subtraction may be right-associative, which would, for example, make 1-2+3 equal –4 instead of 2.)
Variable names shall only contain the lowercase characters a,…,z and cannot be more than 100 characters long. The function names cannot be used as variable names, although a variable name can begin with a function name.
Your parser program will have to store the variables that are declared by the user, along with their corresponding values and you must do this by implementing an open addressing hash table. I can only include the follwing libraries for
input and output, string handling and the calculation of mathematical functions sin and cos.