Thread: Expression Evaluator Contest

  1. #1

    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
    Segmentation Fault: I am an error in which a running program attempts to access memory not allocated to it and core dumps with a segmentation violation error. This is often caused by improper usage of pointers, attempts to access a non-existent or read-only physical memory address, re-use of memory if freed within the same scope, de-referencing a null pointer, or (in C) inadvertently using a non-pointer variable as a pointer.

  2. #2
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903
    Jesus man.. this is tough..!!
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  3. #3
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Is it allowed to enter with code written in 2003/2004?
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  4. #4
    Heh,

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


    - Stack Overflow
    Segmentation Fault: I am an error in which a running program attempts to access memory not allocated to it and core dumps with a segmentation violation error. This is often caused by improper usage of pointers, attempts to access a non-existent or read-only physical memory address, re-use of memory if freed within the same scope, de-referencing a null pointer, or (in C) inadvertently using a non-pointer variable as a pointer.

  5. #5
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    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.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  6. #6
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    I'm in.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  7. #7
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    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.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  8. #8
    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
    Segmentation Fault: I am an error in which a running program attempts to access memory not allocated to it and core dumps with a segmentation violation error. This is often caused by improper usage of pointers, attempts to access a non-existent or read-only physical memory address, re-use of memory if freed within the same scope, de-referencing a null pointer, or (in C) inadvertently using a non-pointer variable as a pointer.

  9. #9
    Software Developer jverkoey's Avatar
    Join Date
    Feb 2003
    Location
    New York
    Posts
    1,905
    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
    Last edited by jverkoey; 03-01-2005 at 04:38 PM.

  10. #10
    Hello,

    Yes you may submit your OST2 parser.


    - Stack Overflow
    Segmentation Fault: I am an error in which a running program attempts to access memory not allocated to it and core dumps with a segmentation violation error. This is often caused by improper usage of pointers, attempts to access a non-existent or read-only physical memory address, re-use of memory if freed within the same scope, de-referencing a null pointer, or (in C) inadvertently using a non-pointer variable as a pointer.

  11. #11
    Software Developer jverkoey's Avatar
    Join Date
    Feb 2003
    Location
    New York
    Posts
    1,905
    Sent.

  12. #12
    Registered User sean345's Avatar
    Join Date
    Mar 2002
    Posts
    346
    I'll enter the contents.
    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
    If cities were built like software is built, the first woodpecker to come along would level civilization.
    Black Frog Studios

  13. #13
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Quote Originally Posted by jverkoey
    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.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  14. #14
    Software Developer jverkoey's Avatar
    Join Date
    Feb 2003
    Location
    New York
    Posts
    1,905
    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

  15. #15
    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
    Segmentation Fault: I am an error in which a running program attempts to access memory not allocated to it and core dumps with a segmentation violation error. This is often caused by improper usage of pointers, attempts to access a non-existent or read-only physical memory address, re-use of memory if freed within the same scope, de-referencing a null pointer, or (in C) inadvertently using a non-pointer variable as a pointer.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with making a Math Expression DLL
    By MindWorX in forum C Programming
    Replies: 19
    Last Post: 07-19-2007, 11:37 PM
  2. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  3. recursion error
    By cchallenged in forum C Programming
    Replies: 2
    Last Post: 12-18-2006, 09:15 AM
  4. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  5. Help! Program to evaluate expression...
    By Unregistered in forum C++ Programming
    Replies: 7
    Last Post: 02-19-2002, 06:20 AM