Lab5: CASIO-fx991

2024-11-18 Admin 写评论


Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due


Lab5: CASIO-fx991

1. Background and Objective

CASIO-fx991, one of the best calculators in the world, excels at calculating mathematical expressions, making it indispensable for us to survive engineering courses. However, have you ever been curious about how CASIO "understands" the expressions and gets the right answers? In this Lab, you will figure this out and create a CASIO fx991 calculator program on your computer with C programming language. In the future, you can combine this algorithm with other hardware to make a real calculator on your own.


Now, your objective is to read commands from a .txt file, and you need to parse these commands and output the results line by line.

2. Syntax and Rules

Input: a txt file named "commands.txt"
Output: stdout (i.e., output to the screen with printf ).

2.1. Basic Operators

" + ", " - ", " * ", " / ", " ^ "," () " with the meaning identical to Matlab.

Notice that " ^ " in C is not the meaning of power. You may use pow() in math.h

The output can all be a " double " type

Example:

input(in commands.txt):


2+ 8
6*(2 +9* 5/1.6)
2^4.6/(3*6)
-3.2+8


stdout:


10.000000
180.750000
1.347304
4.80000


Notice that you need to consider possible spaces between the operator and numbers, as well as multiple parentheses.

You need to use Reverse Polish Expression and the stack data structure to parse and interpret the expressions, which will be covered in part 4 of this file.

2.2. Variables and Assignment Operator(" = ")

We add some Matlab features to our calculator. You need to implement a variable system that can store and use variables in the expressions. (Actually, CASIO 991 can also store variables, but in a different syntax) example:

input(in commands.txt):


a=2.1
b=a^(6+2.8)
cx=a+b^0.9
cx=cx+1


stdout:


2.100000
684.746457
358.532104
359.532104


2.3. Semicolon Requirement
Similar to Matlab, if an expression has " ; " at the end, there will be no output to the screen.

input:


a=2.1;
b=a^(6+2.8);
cx=a+b^0.9;
cx=cx+1


stdout:

359.532104

2.4. Restrictions

To make your life easier, we make some restrictions.

1. We promise that there won't be any syntax errors in the test cases, so you can suppose all the commands in "commands.txt" are valid.

2. In expressions, you needn't consider multiple " ^ " cases. For example, 4^5^6 actually means 4^(5^6) in mathematics, but you needn't consider this case. We won't have test cases like this.
3. Each line of command will consist of less than 100 characters, which means you can use char[120] to store one line of command.
4. There will be at most 20 variables, and a variable's length is at most 10.

4. Reverse Polish Expression

To deal with complex computational commands with multiple operators including parentheses, here we need to implement a useful method: convert the expression to the Reverse Polish Expression first, then calculate the Reverse Polish Expression. To support the Reverse Polish Expression algorithm, you need to know something about the data structure "Stack".

4.1 The Stack Data Structure

A data structure is a way to store data, with algorithms that support operations on the data. Therefore, a stack, as a data structure can have a special way to store data and support different operations on the data. Compared to an array, a basic data structure that you are more familiar with, which allows you to get, delete, add, and modify the value at any place, a stack only supports two basic operations:

1. Push: Add a new element to the end of the stack

2. Pop: remove the element at the end of the stack

Therefore, with these two basic operations, a stack has the property of "First in, Last out" (FILO), thus changing the order of the added elements.

A better way to understand stack is to imagine stack as a badminton tube. The first badminton ball you put in will be the last one you take out.

Then, in order to support the stack data structure, you have to prepare two things: one is the variable to contain the data, and the other is the functions that support the needed operations.

You can simply use an array(with enough space) and an index number(int) to contain the data. The array is like the badminton tube which contains the elements, and the index number indicates the top+1 of the stack. The clever you can immediately notice that the index number can be used to control the size of the stack, therefore helping realize push and pop operations.

Here is a way to initialize an empty stack (which stores elements with " double " type):


double stack[120]={0.0}; // initialize every element as 0.0
int top=0;// top is the number of elements in the array



Figure 1: Illustration of stack initialization


The way to push an element(for example, 4.5) to the stack is:

stack[top++]=4.5;

Explanation: 4.5 is the variable that we want to push into the stack. since stack[top] isn't occupied by any data, we can simply assign 4.5 to stack[top] . Then we need to make top=top+1 because now there's one more element in the stack. We can put these two sentences together, and that's stack[top++]=4.5; (note: the index of array in C begins from 0).


Figure 2: Illustration of operation push


The way to pop an element from the stack is:

element=stack[--top];//suppose variable "element" has already been declared

Explanation: by making top=top-1 , we have already popped out the last element. If we want to know what we have popped out, we need to have element=stack[top-1]; before making "top" smaller. We can put these two sentences together, and that's element=stack[--top];

Figure 3: Illustration of operation pop

It is recommended to write some functions to realize such operations as there's a high risk of "stack overflow", which means the top index gets out of the range of the array.

4.2 Reverse Polish Expression

Reverse Polish expression, also known as postfix expression, can help us deal with an expression. It is used to turn infix expressions into postfix expressions. The term "Polish" in this context refers to its creator, a Polish guy whose name is too difficult to pronounce.

The expression "1+4" is a so-called "Infix expression", which means the operator "+" is in the middle of two corresponding operands. This kind of expression is not friendly to computers because of the operator's priority issues. For example, in the infix expression "1+(1+4)*(5+7)", as a human being, you know how to calculate it in the correct order, but you have no idea how to write a program to make the computer know the right order.

A "Postfix expression", however, makes the computer's life easier. It means to put two operands at the beginning and put the operator at the end of the two operands. In this way, you'll find it easier to calculate its value. For example, the Reverse Polish Expression of the expression "1+4" is "1, 4, +". For the expression "(1+4)*(5+7)", the Reverse Polish Expression is "1, 4, +, 5, 7, +, *".

You are suggested to do some practice to help you understand the human way to change infix expression into postfix expression.

4.3 Turn Infix expression to Reverse Polish expression

How to turn a normal infix expression into reverse Polish expression? That's the hardest part. However, we can use a stack and a set of rules to complete this task.

Follow the rules for an infix expression, and what you print is the reverse polish expression. You need a stack(initially it's empty) to help you.

a. Print out operands(i.e, numbers) 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.step


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.(higher precedence means: "^" > "*" = "/" > "+" = "-" )
f. If the incoming symbol has equal precedence with the top of the stack, pop and print the top of the stack and then 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 the stack. (do rule e-g to them again).
h. At the end of the expression, pop and print all operators on the stack. (No parentheses should remain)
Now what you print is a reverse polish expression.


Please notice that "print" here means store something for further use because our journey doesn't end here. We need the reverse polish expression to calculate the value.
Let's see an example for "(1+4)*(5+7)" step by step:

step

remain
 stack
 print
 comment
0 (1+4)*(5+7)


1 1+4)*(5+7)
 (

2 +4)*(5+7)
 (
 1
3 4)*(5+7)
 (, +
 1 Rule b
4 )*(5+7)
 (, +
 1, 4
5
 *(5+7)
1, 4, +
 Rule d
6
 (5+7)
 *
 1, 4, +
 Rule b
7 5+7)
 *, (
 1, 4, +
8 +7)
 *, (
 1, 4, +, 5
9 7)
 *, (, +
 1, 4, +, 5
 10
10 )
 *, (, +
 1, 4, +, 5, 7
11

1, 4, +, 5, 7, +, *
 Rule d

" 1, 4, +, 5, 7, +, * " is the reverse polish expression.

4.4 Calculate the Reverse Polish Expression

The final step is to calculate the expression and get the result. This is not hard.

We can still use a stack and follow these 2 rules:

a. If you get an operand, push it into a stack.
b. If you get an operator, pop two operands from the stack, calculate the result concerning the operator, and push the result back into the stack.

At the end of the reverse polish expression, only one element remains in the stack. This is exactly the result.

Take " 1, 4, +, 5, 7, +, * " as an example:

step
remain
stack
calculation
0
1, 4, +, 5, 7, +, *

1
4, +, 5, 7, +, *
1
2
+, 5, 7, +, *
1, 4
1 + 4
3
5, 7, +, *
5
4
7, +, *
5, 5
5
+, *
5, 5, 7
5 + 7
6
*
5, 12
5 * 12
7

60

5. General tips

5.1. How to store the Reverse Polish Expression

You may think it's hard to store a Reverse Polish Expression like "1.3, 4.5, +, 3.1, 6, -, /". You won't store it in a C-style string because you will find it hard to calculate its result. So, one feasible way we recommend is to store it in a double array double[] .

So, how could we store operators like '+'? One way is to store its ASCII, for '+', its ASCII is 43. However, it will confuse it with the number 43. But you can use an auxiliary array to mark out whether the element represents a number or an operator's ASCII.

This is an example of how it works:
double RVP[120]={1.3,4.5,'+',3.1,6,'-','/'};

int helper[120]={1,1,2,1,1,2,2};//0 means not occupied, 1 means double, 2 means char

When printing the reverse polish expression into array RVP in 4.3, you also need to update the corresponding place at the helper array, to 1(if it's an operand) or 2(if it's an operator)

Then when you need to operate on one of the elements in the array RVP, for example, RVP[5], you also need to check helper[5] to determine if it's an operator or an operand.

5.2. How to store the variables

Since there will be at most 20 variables, you can use char vars[20][15]={{'0'}}; to store all the variable names. use int varnums=0; to store the total numbers of the variables, and double varvalue[20]; to store the value of the variables.

5.3 More to explore

This document alone may not be enough for you to get over all the problems and understand all the algorithms. Therefore, it is suggested that you explore more about the concepts, algorithms, and explanations related to this lab. Here I list some resources:

To test whether you know how to turn an infix expression into a postfix expression: https://www.mathblog.dk/tools/infix-postfix-converter/

Understand the algorithm: https://youtu.be/7ha78yWRDlE (VPN needed)

https://beltoforion.de/en/muparsersse/implementation.php (a little bit different from ours, but has a similar idea)

https://blog.csdn.net/yuan_xw/article/details/104436091 (written in Chinese but has a very clear gif animation)

6. Rubrics

1. Be able to calculate an expression(2.1): 100 pts
2. Be able to assign a value or expression to a variable, and calculate an expression with variables(2.2): 50pts
3. Be able to suppress the printing(2.3) and complete this lab successfully: 25 pts
4. Lab attendance:25 pts

7. Reminders

I understand that this lab is very hard, especially for beginners. However, your hard work will definitely pay off after the lab. You will have a better understanding of C-style String & Array as well as basic concepts of data structure and algorithm as long as you keep thinking, searching on the internet, and debugging. Of course, you need to start early.

You're highly recommended to write some string-related functions and functions to support stack to help you, for example, insert a string into another string, because you may perform these operations a lot. In this way, your codes can be shorter.Chances are that you will make a lot of mistakes in this lab. So, you need to know how to debug. You shouldn't write all your codes and run all of them afterward. In this case, you'll find your codes not workingand you don't know what's the mistake. Instead, you should debug module-by-module. For example, when you finish the part of transforming reverse polish expressions, you can output them to the screen and see if they meet your expectations. Then you can go on to work on the next part.

Finally, I have to emphasize again that DO NOT ever try to break the Honor Code policy. Avoid high-risk behaviors such as sending your codes to others, publishing your codes on the Internet, submitting other students' codes, etc. We will use an AI-based program to check your codes and anyone who  breaks HC willbe found out.

8. Submission

Your solution should be written into a .c file called lab5.c. Please submit your code to JOJ by compressing the codes into a single zip file in the name format: lab5-[Your Last Name]-[Your First Name]-[Your SJTU ID].zip, for example, lab5-Cao-Wuhao-522370910013.zip. When you come to the lab, show the file to TA according to TA's instructions. After the lab, you need to submit the same zip file to canvas.

9. Acknowledgment

Tang Huijie (TA in VG101 FA2022), VG101 FA2022 lab4
Li Jiawen (TA in VG101 FA2023), VG101 FA2023 lab4

发表评论

电子邮件地址不会被公开。 必填项已用*标注