1. Computing
About.com
C / C++ / C#

Discuss in my forum

Programming Challenge 33 - Evaluate Expressions

Challenge completed

By , About.com Guide

Many scripting languages include some type of an eval function that can take a simple algebraic expression such as 5 * (6-68)/4 and evaluates it. The challenge is to write an evaluator for slightly simpler expressions in C, C++ or C# and process several assignment expressions (one per line) of the form variable=expression as quickly as possible. The fastest correct values wins.

To make it slightly more complex 26 variables are allowed (named a-z) and can be assigned to or read from. All numbers should be held as floating point (single precision will do, use float not double).

a=4.5
b=.0987
c=1/7
b=b+c*a

Operators used are
  • = as in variable=expression
  • + as in c = 6+8, c has the value 14 assigned
  • - as in 6-c would return -8
  • * as in 8*6
  • / as in 4/5
  • ^ power function so 2^3 is 2 cubed = 8.
  • | returns the square root so |9 returns 3

All these operator levels are the same level of precedence and should be evaluated left to right. So 3 + 5/2 = 4 not 5.5 (Add 3 + 5 first = 8) then divide by 2.

No brackets are used and you should detect and handle divide by 0 and print an error for that.

The Input

A text file called input.txt in the same folder as your exe consisting of several assignments of expressions to variables is provided. there is one assignment per line. These will perform several calculations and leave values in y and z. You should print out the final values of y and z. If any errors are found, output a sensible error message on each line and continue.

Astute readers may recognize that the expressions in the input.txt are solving the roots of the quadratic expression x*x-3x-4 =0.

The Output

Please use the timing code from below and time the processing from start to finish after reading the input file until all expressions have been evaluated. If the time to fully evaluate y and z is less than one second then put it in a loop so it takes about 5 seconds and output:

y=
z=
Average time = xxxxxxx secs.

Have fun!

Timing Code

The Results

Congratulations to Jeremy Nicklas whose C++ ran in an astonishing 6.2 microseconds. My apologies to Jonathan Scabich whose C program turned in a very respectable 52 microseconds average time as I had missed Jeremy's entry and wrongly accredited Jonathan as the winner. Mind you the other two entries were no slouches either. Thanks to all four entrants.

  1. Jeremy Nicklas (USA, 27) - C++ Time(secs) = 0.0000062
  2. Jonathan Scabich (USA) - C Time(secs) = 0.000052
  3. A Fabian Ledvina (USA) - C++ Time(secs) = 0.0001775
  4. Ehsan Khakifirooz (Iran, 24) - C# Time(secs) = 0.0022686

Rules

This is for glory only. About.com does not permit prizes to be given.

Please submit your source code and the output file to the cplus@aboutguide.com?subject=Programming Challenge 33 email address with the subject line Programming Challenge 33.

It must compile with Open Watcom, Microsoft Visual C++ 2005/2008 Express Edition/Microsoft Visual Studio 2003/2005/2008 or Borland Turbo C++ Explorer, Microsoft Visual C# 2005/2008 Express Edition or GCC/G++. If it doesn't compile, it can't be run so is automatically disqualified.

Please include your name, age (optional), blog/website url (optional) and country. Your email address will not be kept, used or displayed except to acknowledge your challenge entry. You can submit as many entries as you like before the deadline which is March 31 2010.

The top ten entries will be listed, judged purely on points. A condition of entry is that you allow your source code to be published on this website, with full credits to you as the author.

More Programming Challenges

©2013 About.com. All rights reserved.