Expression Evaluator Contest

Printable View

02-28-2005
Stack Overflow

Expression Evaluator Contest
Expression Evaluator Contest

Schedule / Deadline
Start Date: March 1st, 2005 [Tuesday]
End Date: March 31st, 2005 [Thursday]

Submissions
If you choose to enter, please reply stating that you have entered the contest, and before the Contest deadline you must enter a submission that meets the stated requirements and send it to the submission officer via email or private message. E-mail is preferred.

E-mail: [email protected]
PM: Stack Overflow

Introduction
An expression evaluator reads in user inputted infix expression, and converts it to postfix. For the purpose, implements stack and queue abstract data types (ADT) using pointers. Each integer and operator is kept in specially designed token object to allow different data types to be held on the same data structures. Going through the steps of conversion involves checking the priority of the operator. After evaluation the stack contains one value - the final answer, which is given back to the user.

Details
Create your own expression evaluator in pure C or C++. It must have a console-based interface.
Bonus [5 points]: Display the infix expression in reverse polish notation. For example, the expression 3 * (4 + 7) would be written as 3 4 7 + *.

Summary
Any expression in the standard form like "2*3-4/5" is an Infix (Inorder) expression.
The Postfix (Postorder) form of the above expression is "23*45/-".
The Prefix (Preorder) form of "(1 + 2) * 3" is "* 3 + 1 2" or "* + 1 2 3"

Contest Rules
Below are the current contest rules and regulations.

I. Official Rules
I.I You may only submit one entry per contest, and it must have been submitted between the contest start and end dates.

I.II If you submitted your entry, you are permitted to re-enter your submission between the contest start and end dates.

I.III Entries submitted should be:
- Substantially the developer's original design
- Substantially the developer's original programming
II. Judging Categories
II.I Submitted code will be judged based on the following criteria:

Creativity (0 - 5)
Make your concept new, or give an old one a unique twist.

Compilation (0 - 5)
How clean the build process is.

Efficiency (0 - 5)
Dependant upon necessary or unnecessary resources used by your program.

Portability (0 - 5)
How well it compiles on multiple platforms.

Elegance (0 - 5)
The code's layout scheme and organization.

Best Code Score: 25 (Excluding Additional Bonus Points)

- Stack Overflow
02-28-2005
The Brain

Jesus man.. this is tough..!!
02-28-2005
Sang-drax

Is it allowed to enter with code written in 2003/2004? :p
02-28-2005
Stack Overflow

Heh,

Any year is fine. Well, preferbaly after 1989. ;)
Oh, and written in C or C++; not C/C++. :cool:

- Stack Overflow
02-28-2005
Sang-drax

OK, I'm in, but I will submit that code I wrote a while ago.
If I remember correctly Prelude provided some code for inverting matrices.
03-01-2005
pianorain

I'm in.
03-01-2005
CornedBee

Why do we need to write our own stacks and queues? I mean, what's the C++ standard for, if not that?

I may be in, need to check my schedule. Or rather make it.
03-01-2005
Stack Overflow

Heh,

Alright. Well you don't have to write your own stacks and queues if you use C++. It was mainly an explanation of how expression evaluators operate.

- Stack Overflow
03-01-2005
jverkoey

May I submit my OST2 parser...? Here's what it supports (and all infix to postfix converted and optimized):

+ - / * % ^ && || == != += -= *= /= umm.....what else
functions, variables, arrays, unlimited parenthesis nesting, ability to change the accuracy....compilation in two steps, execution in one...hmmm, I'm probably missing some operators....I'll submit the code later tonight when I get home.

*drools* I love this kinda stuff anyways. I'll see if I can optimize my parser at all. OST2 Release #10's got this parser in it, but I've shelled out the code and used it in other projects like my Physics Solver (where you type in the known variables and it will solve for the requested unknowns). This is definitely the area of coding I like working in :D
03-01-2005
Stack Overflow

Hello,

Yes you may submit your OST2 parser. :cool:

- Stack Overflow
03-01-2005
jverkoey

Sent.
03-01-2005
sean345

I'll enter the contents.

Quote:

An expression evaluator reads in user inputted infix expression, and converts it to postfix.

When you say this, do you mean that it is a requirement of the contest that the expression evaluator convert the infix to postfix or is this just a suggestion?

- Sean
03-02-2005
Sang-drax

Quote:

Originally Posted by jverkoey

May I submit my OST2 parser...?
[...]
This is definitely the area of coding I like working in :D

Yes, I've checked out your language before and it's definitely interesting, but I'm not fond of some of the syntax, like the BEGIN; VARIABLES; commands for example.

I've also created my own language. I've mostly worked on the syntax, so it's not capable of actually doing as much as your language.
http://www.strandmark.com/omicron.shtml

I won't win though, as 40% of the score is dedicated to compilation/portability. :D
03-02-2005
jverkoey

When I originally designed the syntax, I had designed it with "simplicity" in mind, as in, simplifying and reducing as much of the code as possible. I realised after a while though that simplifying code is definitely not a good idea and it's also allowed me to greatly appreciate C/C++ and other languages with OOP and advanced features. Lately my language has kind of been a dead project, Release #10 still hasn't officially been released, but the main reason I've stopped is because my language isn't really GOOD for anything, heh. I've been trying to come up with something that it could actually be used for...and so far I've only thought of using it in games because I shelled out the parser to a DLL that you can import....*shrugs*

But hey, if you want to exchange ideas on our parsers or anything, feel free to IM me, I'd love to hear how someone else put theirs together.

msn: [email protected]
aim: TheJeffFiles com
03-02-2005
Stack Overflow

Quote:

Originally Posted by sean345

When you say this, do you mean that it is a requirement of the contest that the expression evaluator convert the infix to postfix or is this just a suggestion?

Well,

Expression evaluators I've seen do this for evaluation. To our surprise Infix notations are not as simple as they seem, especially while evaluating them. To evaluate an infix expression we need to consider Operators' Priority and Associativity.

For example, will expression 3+5*4 evaluate to 32 i.e. (3+5)*4 or to 23 i.e. 3+(5*4). To solve this problem Precedence or Priority of the operators were defined. Operator precedence governs evaluation order. An operator with higher precedence is applied before an operator with lower precedence.

For further documentation: CodePedia: Expressions, Conversion and Evaluation with C

- Stack Overflow
03-02-2005
CornedBee

Speaking of which, what operators must the thing support, and what are the precedence rules it must follow?
03-02-2005
Stack Overflow
Hello,

The standard operators are +, -, *, /, !, and ^; where ^ represents the exponential operator, and ! represents factorial.

The link I provided earlier has a figure that shows Operator Precedence in descending order. Also, in an infix expression, the operators do not appear (from left to right) in the order in which they are to be carried out. Instead, we use parentheses and precedence rules to indicate the order in which they should be done. In the absence of parentheses, the following precedence rules are in effect:
- Exponentiation has the highest precedence. Perform exponentiations in order first, from left to right.
- Multiplication and division have the next-highest precedence. After performing all exponentiations, perform multiplications and divisions in order, from left to right.
- Addition and subtraction have the lowest precedence. After performing all multiplications and divisions, perform additions and subtractions in order, from left to right.
In actuality, exponentiation is right-associative, but we'll keep things simple.

- Stack Overflow
03-27-2005
elad

My solution was emailed to you. I view it as a no-nonsense response. Thanks for the challenge.
03-29-2005
Stack Overflow

Hello,

Submission received. Thanks for participating. :cool:

- Stack Overflow
03-29-2005
Sang-drax

Did you recieve my submission as well?

I submitted the old code, I wasn't even able to make it compile on VC++.NET.
03-29-2005
Stack Overflow

Hello,

Well, I just checked my eMail this morning, and I did receive it. Heh, it's getting close to the deadline; it's time I grade all of the submissions. I'm about to look over the eMail.

Thanks for participating :cool:

- Stack Overflow