讲解program语言编程、c++程序设计调试、辅导c/c++编程

日期：2020-11-12 08:36

Lab5 – Interpreter
In this lab, you will write a simple interpreter whose language syntax is similar to that in
MATLAB. Through this lab, you will learn to deal with strings and implement a complicated
program step by step.
Input: A file named “commands.txt”.
Output: Standard output
Syntax:
1. Basic computation operations
A. We need to implement basic mathematical operations including ‘+’, ‘-’, ‘*’, ‘/’, ‘^’.
For simplicity, one line only contains one sentence.
If there is a semicolon at the end of the sentence, the interpreter won’t output the result,
otherwise, it will output the result in a new line.
Note: there may exist spaces before/after the operators.
Sample:
Input: Output:
B. Also, there will appear variables in the sentence whose values need to be recorded.
If there is ‘=’ in the sentence, the sentence will be in the form “variable_name = balabala”,
note that “balabala” may also contain variables that has been given certain values.
Note: remember to record new variables that appear for the first time with its value as well
as update the values of variables that always exist.
Note: the rules in part A are also valid in part B.
Sample:
Input: Output:
2. Standard I/O
To control the output format, we require the interpreter to execute a simple fprintf command.
The following expressions are valid:
fprintf(“Good Luck in Lab 5!\n”);
fprintf(“ans = %f.\n”, ans);
fprintf(“ans = %f.\n”, 3+5);
Note: you can only use float (%f) in this interpreter language, but feel free to use double type
in you C program.
Sample:
1. Input file “commands.txt”
Output
2. Input file “commands.txt”
Output
Hints:
Start early!
Feel free to use the algorithms online.
a = 1+3
a = a + (5 * 2) / 3
7
a = a/2;
fprintf(“ans = %f.\n”, a);
fprintf(“End\n”);
4
7.3333
7
ans = 3.6667
End
a = 400-9;
b = 4^2-2;
b = b*a;
a = (2*5)^(1+2)*9+880/2/2/2;
c = b*10000+a;
fprintf(“If you are in danger,
please Call %f.\n”, c);
If you are in danger, please call 54749110.000000.
Appendix:
To deal with complex computational commands with multiple operators including parentheses, here
provides a useful method: convert the expression to reverse polish expression first, then calculate
the reverse polish expression.
A. Stack
Stack is a data structure with two basic operations:
i. Push: to add an element to the top of the stack.
ii. Pop: to pop an element from the top of the stack.
In C, to implement a stack, we simply create an array which represents the content in the stack
as well as an integer which indicated the top of the stack (stack top pointer).
Sample:
double stack[MAX_ELTS];
int top = 0;
Then, the push operation can be written as:
stack[top++] = elt;
the pop operation can be written as:
elt = stack[--top]；
B. How to convert a computational command to reverse polish expression
Follow the rules:
a. Print out operands as they arrive.
b. If the stack is empty or contains a left parenthesis on top, push the incoming operator onto
the stack.
c. If the incoming symbol is a left parenthesis, push it on the stack.
d. If the incoming symbol is a right parenthesis, pop the stack and print the operators until
you see a left parenthesis. Discard the pair of parentheses.
e. If the incoming symbol has higher precedence than the top of the stack, push it on the stack.
f. If the incoming symbol has equal precedence with the top of the stack, use association. If
the association is left to right, pop and print the top of the stack and then push the incoming
operator. If the association is right to left, push the incoming operator.
g. If the incoming symbol has lower precedence than the symbol on the top of the stack, pop
the stack and print the top operator. Then test the incoming operator against the new top of
stack.
h. At the end of the expression, pop and print all operators on the stack. (No parentheses
should remain.)
Sample:
(1+2)*(3-5)
stack:
1+2) *(3-5)
stack: (
+2) *(3-5)
print: 1
stack: (
2) *(3-5)
print: 1
stack: (, +
) *(3-5)
print: 1, 2
stack: (, +
*(3-5)
print: 1, 2, +
stack:
(3-5)
print: 1, 2, +
stack: *
3-5)
print: 1, 2, +
stack: *, (
-5)
print: 1, 2, +, 3
stack: *, (
5)
print: 1, 2, +, 3
stack: *, (, -
)
print: 1, 2, +, 3, 5
stack: *, (, -
print: 1, 2, +, 3, 5, -, *
stack:
“(1+2)*(3-5)” is converted to “1, 2, +, 3, 5, -, *” and we just need to compute the latter!
C. How to calculate on reverse polish expression
The reverse polish expression is an expression that puts the operator behind the operand, i.e. “3,
5, +” means “3+5” in common sense.
It’s very easy to evaluate a reverse polish expression using stack. For example: To evaluate “1,
2, +, 3, 5, -, *”, we read from the first element and push them into a stack if it’s a number. If it’s
an operator, pop two numbers out, do the calculation and push them back to the stack.
Sample:
1, 2, +, 3, 5, -, *
stack:
2, +, 3, 5, -, *
stack: 1
+, 3, 5, -, *
stack: 1, 2
3, 5, -, *
stack: 3
5, -, *
stack: 3, 3
-, *
stack: 3, 3,5
*
stack: 3, -2
stack: -6
-6 is the final result.