article

Action executed in 0.000

Stack, Expression Evaluation Challenge

Implement a stack. Use it to evaluate a simple mathematical expression. This expression will not have parentheses. It will use only plus, minus, multiply, and divide operators. The operands (input) will be integers, although output may be rational due to division. You may or may not use recursion. All code must be written by you.

Of course i'd like to see recursion. But if you think that's impossible then don't. When you see my example you will be proven wrong.

You swap out a stack for another data structure, but once again, don't wimp out.

Any code that is not used is seen wasteful and a bore to my eyes.

Comments

When you see my example you will be proven wrong. Your example, eh? :) BTW.. Im altering my queue into a stack and omitting my additional challenge of solving an equation. Perhaps if I get bored someday Ill finish the challenge, but (as those of you on SILC know..) Im too frustrated at my waste of time thusfar to continue.
parent post: Stack, Expression Evaluation Challenge
notify me: yes

Questions and Assumptions

tags: code, C, integer
The code must be in C (otherwise this is a waste of time), Can we assume that the digits are between 0 and 9, or do we need to deal with reading full integers off the command line?
parent post: Stack, Expression Evaluation Challenge
notify me: yes

Why recursion if we have to write a stack?

tags:
See the title.
parent post: Stack, Expression Evaluation Challenge
notify me: no

Language, Parentheses, Input, and KISS

tags:

We agreed on two amendments. I'm suggest two more.

First i just want to remind people that this project should try to match the spirit of the conversation we had on IRC.

The language must be C. Really the language is not the focus here; the algorithm is.

Input may have parenthesis. All tokens will be separated by space. Integers (input) will have at most 5 digits. Output must be fully resolved, ie it must not be a fraction. Output must be base 10. The number of significant digits does not matter, as long as the answer is correct. Assume all operators are explicitly given. No exponents. Here's an example: (12 + (4 / 83) * 3) - 1. Assume there are no superfluous parentheses.

I suggest reading input from a file, one expression per line. This way we can have common test input and we can run n tests at a time without retyping them.

Bonus points (read bragging rights) to candidates who keep it simple.

parent post: Stack, Expression Evaluation Challenge
notify me: yes

Terminology

tags:
On the matter of expressions, terms, and factors, here's a grammar in near-BNF. It may or may not help you.

expression -> term [+- term]?

term -> factor [*/ factor]?

factor -> number | '(' expression ')'

( 2 ) + 3 * 5 has 3 numbers, 4 factors, 3 terms, and 2 expressions. I'll try to draw a tree.

    e
  t   t
 f   f f
e    # #
t    3 5
f
#
2
parent post: Stack, Expression Evaluation Challenge
notify me: yes

Sample Input and Ouput

tags:
Here are two files for sample input and output. If there are any issues or errors, email me. I'l make corrections and post version 2.
input.txt output.txt

There's tolerance on the non-integers.

parent post: Stack, Expression Evaluation Challenge
notify me: yes

Regular Grammar

tags:
I figured that coming up with a regular grammar for an expression would help make writing an algorithm to turn it into a tree easier. What would that look like? E = (E) = E op E, E op? Ideas... (Bearing in mind that I want to be able to arbitrarily add operations to this process, so it's terribly important to get the parsing correct.)
parent post: Stack, Expression Evaluation Challenge
notify me: no

(1) ?

tags:
Is ( 1 ) a valid expression? There aren't two operands. Just curious.
parent post: Stack, Expression Evaluation Challenge
notify me: yes

Regarding ( 1 )

tags:
Yes. Here's the abstract syntax tree: expression = term = factor = ( expression ) = ( term ) = ( factor ) = ( number ) = ( 1 ). Two operands are not required. In fact an operator is not required.
parent post: Stack, Expression Evaluation Challenge
notify me: yes

Post a Comment

* indicates a required field
anonymous (If you want to identify yourself, please sign in first.)
required This field is required.

Max size is 2 MB, aspect ratio 3:4 width:height
required This field is required.
Please include a short description.
required This field is required.

480 characters remaining.
is public

(Use this field if you have to. 3000 characters remaining.)
1 quarter, 2 pennies, 1 dime + 100

Trackback URL

http://derocher.org/~brian//trackback.php?ParentId=577

form