Expression Evaluator Contest

[Stack Overflow]

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

[The Brain]

Jesus man.. this is tough..!!

[Sang-drax]

Is it allowed to enter with code written in 2003/2004?

[Stack Overflow]

Heh,

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


- Stack Overflow

[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.

[pianorain]

I'm in.

[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.

[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

[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

[Stack Overflow]

Hello,

Yes you may submit your OST2 parser.


- Stack Overflow

[jverkoey]

Sent.

[Sang-drax]

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

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.

[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

[CornedBee]

Speaking of which, what operators must the thing support, and what are the precedence rules it must follow?

[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