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.
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?
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.
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.
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.
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.
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: