micro-mini interpreter challenge

Implement the algorithms on expression evaluation using the ADT Stack.

The input will come from a text file with the following requirements:
1. There must be an output statement that will display a string on the screen. The string can be any string specified by the user. Every time the program reads the output statement, it must display whatever it is inside the double quotations. The statement must be terminated with a semicolon.
2. An input statement must also be used for reading an integer from the keyboard. It will read one integer at a time. You can have any number of ‘read’ statements to be interpreted.
3. The program must evaluate the equation/expression given in the input text file.
The output will be from the screen.

Example:
Input.txt
print “Hello I am Steve:”;
print “Please input a number:”;
read num1
print “Please input another number:”;
read num2
print “Please input another number:”;
read num3
num4 = (num1 + num2) * (num1 / 2) + ( num3 ^ 2);
print “num4 is”, num4;

Output:
Hello I am Steve
Please input a number: 8
Please input another number: 2
Please input another number: 2
num4 is (8 + 2) * (8 / 2) + (2 ^ 2) = 44

Scope and Limitations:
1. There must be the operations, addition, subtraction, multiplication, division and exponentiation.
2. Parenthesis are included.
3. No variable declarations required.
4. Only single digit numbers will be processed.
5. Must use the algorithms for expression evaluation using stacks.
a. The infix expression must be converted to postfix or prefix
b. The postfix or prefix expression must be evaluated
6. Must output an error message when the expression is incorrectly formed.
What is your code so far and what exactly is/are you question(s)?
Some of the limitations are fairly restrictive:

4. Only single digit numbers will be processed.
The example output cannot be accomodated with single digits ('44' contains two digits). I don't see any reason not to accept any number representable by a standard int.

5.a. The infix expression must be converted to postfix or prefix
Why? Conversion between infix and another-fix involve dealing with parse trees (either implicitly or explicitly), which is not strictly necessary. I would have written it without.

[edit]
Last line of output requires caching information about the expression. It should read:

    num4 is44

Notice the lack of space between "is" and "44" because of the source print statement.


[edit 2]
Why the semicolon at the end of print and assignment statements but not at the end of read statements?
Last edited on
so far, I'm okay with the conversions...

I'm having trouble with the input text file part using c++
@Duoas

5.a. The infix expression must be converted to postfix or prefix
Why? Conversion between infix and another-fix involve dealing with parse trees (either implicitly or explicitly), which is not strictly necessary. I would have written it without.


Implement the algorithms on expression evaluation using the ADT Stack.
Use of a stack does not imply prefix or postfix.
@Duoas

Use of a stack does not imply prefix or postfix


it does imply if you understand something in infix, prefix and postfix forms of recording expressions.
Last edited on
it does imply if you understand something in infix, prefix and postfix forms of recording expressions.

Very rude.

Perhaps it is you who lack understanding about the many uses to which stacks may be put for parsing arithmetic expressions -- prefix, postfix, and infix.
vlad wrote:
Are you an idiot? There is clear written in the assignment... [stuff about requiring conversion from infix to postfix or prefix stacks]

I didn't report you, but I would have.

My only idiocy is asking why the infix->foofix conversion must be done.

Of course stacks can be used for many purposes. However stack is not very appropriate to evaluate infix expressions.

Bull.

It is the difficulty to evaluate infix expressions with stacks was the reason of inventing postfix and prefix recording of expressions.

Really? We are rewriting history now?

recording expressions

A small nit-pick, but we aren't recording expressions, we are evaluating them. A record of the expression already exists in the input.

Though, I might concede the point if the OP clarifies that last output, as I wondered about it in the first edit I made in my first post above.
Sorry to intrude

what is a "recording expressions" ?
Any expression can be recorded (or maybe it would be better to say written) in different forms: in the infix form, postix form or prefix form depending on where operators are placed relative to their operands.
Last edited on
I still dont understand can you give me an expamle of an expression and its recoreding(If am right)
in infix form, postix form or prefix form
?

thanks
This is the infix record of an expression

(8 + 2) * (8 / 2) + (2 ^ 2) = 44

binary operators are placed between their operands

This is the postfix record of the expression

8 2 + 8 2 / * 2 2 ^ + = 44

binary operators are placed after their operands.

In the prefix form binary operators are placed before their operands.
closed account (o1vk4iN6)
Duoas wrote:
Really? We are rewriting history now?


Seems the reason postfix was invented was simply someone trying to create a notation without parentheses. Wonder if it was a misinformed teacher that told Vlad otherwise.
Last edited on
Actually, Vlad isn't far off. He just keeps drawing non-factual conclusions and stating them as fact.

The original "Polish Notation" was invented by some mathematician from Poland as more or less of an intellectual exercise while messing with logic statements. (It seems he was trying for a more efficient notation than was available to him.)

RPN really became well known outside of mathematical circles when HP started advertising it with their calculators. In terms of hardware, they were looking for an efficient circuit design. Requiring consumers to enter stuff in RPN wasn't too much of a leap, and made their calculators more powerful than most everything else on the market.

That RPN lends itself to easy and simple evaluation on a stack is a convenient fact that many have employed -- and hence their common association in CS literature.

But stacks have existed independently of RPN both before and after it became so well-known. All it takes is a pair of stacks to handle an infix expression in a single pass.


[edit]
Oh yeah, this is posted as a "challenge", but now I wonder:

Is this just the OP having homework trouble?
Last edited on
@Duoas ,For me, It's nothing more passion than waitting you to post in this website. Thanks for the info.
Last edited on
Topic archived. No new replies allowed.