LAB4--Interpreter Lifesaver

Posted on Edited on In Views: Word count in article: 12k Reading time ≈ 11 mins.

The objective is to read commands from a txt file, parse these commands and output the results line by line. Just like what MATLAB does.

写在前面

首先不要被interpreter吓到，这只是一个功能基本的小程序，远没有到写编译器（compiler）的程度！不要慌，这是可以实现的！

整个实现过程是由小到大，由少到多的，基本流程如下：

  • 实现读写数据
  • 实现逆波兰加减乘除
  • 实现逆波兰括号
  • 实现逆波兰式完整转化
  • 实现分割操作符与操作数
  • 实现逆波兰式的计算
  • 实现对负数的识别与计算
  • 实现对任意表达式的计算（Milestone）
  • 实现变量赋值式的转化
  • 实现变量的识别
  • 实现变量的数值存储与使用
  • 实现有变量式子的计算
  • 实现变量值变化后式子的计算
  • 实现分号功能
  • 通过JOJ！

然而本文档并不会每一步给出指导（懒）只会给出一些关键问题的解答，如果还有疑惑，请首先使用你的大脑，再使用搜索引擎，再使用TA，最后使用你的倒霉室友。

注：本文档中的大部分代码是伪代码（seudo code），仅作为基本的示范，不可直接复制黏贴！请你理解后模仿写出属于自己的代码！

stack的操作与定义

栈的性质

栈是一种特殊的数组，数组中的元素先进后出，后进先出，可以类比为一个羽毛球桶，先进去的羽毛球最后面才能拿出来。为了体现“先进后出，后进先出”的重要特性，我们规定push与pop两种操作。push将元素塞入数组最上方，pop将数组最上方的元素弹走。

push（压栈）pop（弹栈）：

1
2
3
4
int push(char *stack, int top, char element);       // push char
int push_d(double *stack, int top, double element); // push double
int pop(char *stack, int top);                      // pop char
int pop_d(double *stack, int top);                  // pop double

考虑到pop与push均为栈的常用操作，因此通过自定义函数来实现。

自定义时注意以下三点：

  1. pop/push 完后，top在哪？
  2. pop/push 的对象元素是谁？
  3. pop/push 的目标数组是谁？
  4. 栈的数据类型？
  5. 将以上问题的答案作为你的函数参数/输出。

Sample Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
int push(char *stack, int top, char input){
    stack[top++] = input;
    return top;
}

int pop(char *stack, int top){
    if (top == 0)
    {
        return 0;
    }
    out1 = stack[--top];
    return top;
}

自定义好stack操作函数后，开一个新的practice.c 熟练你的stack操作！

修改自己的pop与push函数，使其符合自己的思维习惯与逻辑。

注意：只有你知道你的stack应该怎么操作！

Sample Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>

char out;
int push(char *stack, int top, char element);
int pop(char *stack, int top);

int main()
{
    char stack1[120];
    char stack2[120];
    int top1 = 0;
    int top2 = 0;//top初始值为0，否则会越界
    top1 = push(stack1, top1, 'a');
    top1 = push(stack1, top1, 'b');
    top2 = push(stack2, top2, 'c');
    top1 = pop(stack1, top1);
    top2 = pop(stack2, top2);
    printf("%c\n", stack1[top1]);
    printf("%c\n", stack2[top1]);
    return 0;
}

int push(char*stack, int top, char input){
    stack[top++] = input;//注意：这里的top++与++top天差地别！自己思考为什么！
    return top;
}

int pop(char*stack, int top){
    if (top == 0)
        return -1;
    out = stack[--top];//注意：这里的--top与top--天差地别！自己思考为什么！
    return top;
}

stack在逆波兰表达式中的实战

逆波兰表达式RPE（Reverse Polish Expression）

毫无疑问，lab4的description在放屁。如果你仍然对RPE有不解之处，或者你无法熟练地人工写出一个正常表达式的逆波兰表达式，请你先理解逆波兰表达式的操作后再开始coding！

逆波兰表达式由某个波兰人发明，由于发明者名字太难读，所以取名“Polish”。逆波兰表达式的本质是将一个中缀表达式(infix)，i.e.操作符（operator）前后连接两个操作数（operand）（e.g. (0 /a+ 0 / 1+ 0/3 + 0/a + b * 2.5)* b^(-2)）变为后缀表达式(postfix)，i.e.，操作符在操作数的后面 （e.g. ,0,a,/,0,1,/,+,0,3,/,+,0,a,/,+,b,2.5,,+,b,0,2,-,^,）由此便可以通过栈的数据结构便于计算机的运算与操作。

逆波兰表达式的转化

预备工作

要实现逆波兰表达式的转换，你需要三个数组：

  1. 待转换式子的数组 infix
  2. 放符号的load栈 load_stack
  3. print最终转换后结果的输出栈 RPE

开始转换

从左至右扫描中缀表达式。

遇到操作数时，将其压入转换后结果的输出栈RPE。

遇到运算符时，比较其与 load_stack栈顶运算符的优先级：

  1. 如果load_stack为空，或栈顶运算符为左括号(，则直接将此运算符入栈。

  2. 否则，若优先级小于或等于栈顶运算符优先级，将load_stack栈顶的运算符弹出并压入到RPE中。将当前运算符压入栈中load_stack中

  3. 再次转到 1 与load_stack中新的栈顶运算符相比较。

遇到括号时：

  1. 如果是左括号(，则直接压入load_stack。

  2. 如果是右括号)，则依次弹出load_stack栈顶的运算符，并压入RPE，直到遇到左括号为止，此时将这一对括号丢弃； 重复步骤2至5，直到表达式的最右边。

  3. 将load_stack中剩余的运算符依次弹出并压入RPE。

整个流程都非常抽象，表格法并不直观。所以强烈建议看视频或者动图进行直观理解。

可参考资源：

https://blog.csdn.net/yuan_xw/article/details/104436091

https://youtu.be/7ha78yWRDlE

完美的逆波兰表达式应该只有数字与加减乘除等，没有括号！

实现

在基本理解转换过程后，拿几个式子进行人工计算！可用这个网站https://www.mathblog.dk/tools/infix-postfix-converter/ 进行检验。

感觉自己基本掌握了之后，就开始coding吧！

在转换之前，请你首先解决这个不难但是总是实现不了的问题：

如何将读写txt文本的数据？

  1. 推荐以下函数：

fopen(), feof() ,fgets()

他们的具体功能与使用请自己搜索（真的不难！）

  1. 文本数据可以存放在一个二维数组中：
1
char data[LINE][LENGTH]
  1. 然后你就应该知道怎么办啦！

编程时思考以下问题：

  1. 你眼前有三个数组，分别给他们取上你喜欢并且易于识别的名字
  2. 这三个数组哪两个是stack？每个stack的top又如何设定？
  3. 符号的优先级该如何比较？hint：写一个比较优先级的函数。
  4. 括号的操作应该怎么办？弹出load_stack元素时会不会弹空？
  5. 别忘记最后清空！

Debug

转化过程中，你将会碰到各种bug报错，以下列举一些常见报错：

  1. segmentation fault：分割错误，一般可以诊断为死循环。

  2. 如图错误：

截屏2022-11-01 19.27.41

Explanation: index -1意思就是你的数组指针指到-1的位置，这是非常危险的，因为-1位置可能是别的数组！所以仔细查看报错行的循环/数组是否存在越界行为。一般容易发生在括号的处理中。

  1. 如图错误
在线平台报错信息

Explanation: 可以诊断为某个数组越界。根本原因是你的输入文件名和joj的输入文件名不一样！很傻逼的报错。

  1. 其他报错

如果碰到其他抽象的错误，可以通过注释法查找。

注释法：把你觉得可能有问题的代码注释掉，看看还有没有相同类型的报错。

逆波兰表达式的计算

在确保正确的逆波兰表达式后，计算则相对简单不容易出错。手动计算方法如下：

  1. 找到一个操作符

  2. 找该操作符前两个操作数

  3. 将这两个操作数按照该操作符进行计算，得出结果

  4. 将这两个操作数与操作符删掉，替换成3中计算的结果

如何让计算机实现以上操作过程？

但是聪明的你应该想到，要想计算必须要让计算机认识哪个是操作符，哪个是操作数

因此我们不得不进行句法分析

句法分析（parsing）

句法分析，顾名思义就是让计算机能够识别字符串中的合法的词句。

1
2
3
4
5
6
7
8
9
10
11
Eg1：一个string：iloveprettygirls 

你的眼里：i love pretty girls

计算机眼里：i l o v e p r e t t y g i r l s 

Eg2：一个string：25+36/0.23-(34-3)

你的眼里：25+36/0.23-(34-3)

计算机眼里：2 5 + 3 6 / 0 . 2 3 - ( 3 4 - 3 )

所以，我们的目的就是让计算机眼里看出来的和我们人类眼里看出来的是一样的，这就是句法分析。

那如何句法分析呢？在这里给出一个hint：在push符号的时候，顺便push一个分隔符进去；push数字、小数点时就不push分隔符。

我想其他细节应该你可以解决！

Sample Code:

1
2
3
4
5
6
char char_RPE[1200] = {0};   // RPE=Reverse Polish Expression; 转换后的逆波兰表达式；字符类型
char stack[1200] = {0};      //存放符号的stack
int top_stack = 0;    // stack 指针
int top_char_RPE = 0; // RPE指针
top_char_RPE = push(char_RPE, top_char_RPE, '|'); //push'|'作为分隔符，分割数字与符号，头尾都有分隔符
top_char_RPE = push(char_RPE, top_char_RPE, pop(stack));

类型转换

在计算时，你一定注意到了计算机不可能拿着字符去计算，所以我们还需要把分割好的词句变为double。

在前面的基础上，我们可以通过分隔符获得相应的字符串，然后通过这个式子double_RPE[i] = strtod([分割后的一个字符串], NULL)进行转化！

P.S. strtod的具体功能与语法请自行搜索

但是，这样转换就会带来问题，操作符进行strtod后便会变成0.00000！这无疑影响我们后续计算！

所以，我们引入辅助数组helper[ ]来判断这个字符串是数字还是操作符。

Sample Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int helper[1200] = {0};             //辅助数组 用来判断double_RPE中的数字与符号
if ((char_RPE[i] >= '0' && char_RPE[i] <= '9') || (char_RPE[i] == '.'))
{
      get_string[m] = char_RPE[i];
      m = m + 1;
      helper[j] = 1;
}
if (char_RPE[x] == '+')
{
  	  helper[i] = 2;
                }
We wish to get:
double_RPE[120]={1.3,4.5,0.00,3.1,6,0.00,0.00};
		helper[120]={1  ,1  ,2   ,1  ,1,3   ,5};//2~5分别表示加减乘除乘方

2.3.4 计算

基本准备

为了贯彻栈的“先进后出”的思想，我们不妨先把得到的double_RPE与对应的helper逆序排列。同时，我们准备好计算时的缓冲栈load_cal_stack与计算栈cal_stack.

1
2
3
4
5
6
7
double RPE_Reverse[120] = {0.0}; 						//逆序RPE 便于计算
double helper_Reverse[120] = {1.0};     		//逆序辅助数组 便于计算
double load_cal_stack[120] = {0.0};         //缓存栈 用于存储运算后的结果
double cal_stack[120] = {0.0};    					//计算栈 用于运算 
int top_cal_stack = 0;      								//计算栈指针
int top_load_stack = 0;     								//缓冲栈指针
int top_helper_and_RPE = MAX_DOUBLE_RPE; 		// double型逆波兰指针

不难发现，我们眼前共有四个数组/栈，然后我们手里有三个“指针”(top)，即表示数组中元素坐标的index.

其中top_helper_and_RPE同时控制RPE与helper,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

```top_load_stack```控制```load_stack```

##### 弹栈入栈

其实就是把2.3.1中的过程以栈的形式体现出来，可参考如下代码：

**Sample code**

```c
//将double RPE的元素弹入缓冲栈
top_helper_and_RPE = pop_d(RPE_Reverse, top_helper_and_RPE);
top_load_stack = push_d(load_stack, top_load_stack, out);
//以“+”为例：
//'+' 碰到运算符后从缓冲栈中弹三个进入计算栈开始算 算完了弹回缓冲栈 后面同理
if (helper[top_helper] == 2)
{
  	for (int i = 0; i < 3; i++)
    {
         top_load_stack = pop_d(load_stack, top_load_stack);
         top_cal_stack = push_d(calculate_stack, top_cal_stack, out2);
    }
double sum = 0;
sum = cal_stack[top_cal_stack - 1] + cal_stack[top_cal_stack];
}

最后load_stack剩下的那个数就是最后结果啦！

负数处理

虽然我们已经能够很好地转化并计算一些逆波兰表达式，然而逆波兰表达式先天性存在一个小bug——他不支持负数的运算。按照我们之前的算法，碰到负数，例如-1时，我们会把他分割为"-","1"而不是"-1". 因此在计算时碰到负数会出现缺少一个操作数的情况，从而无法获得结果。所以，我们需要对式子中的负数进行预处理。

这个问题确实令人烦躁，但是静下心来仔细思考我们会发现，所谓负数无非是这两种情况：

  1. 第一个字符为减号

  2. 括号内第一个字符是减号

那么我们只需分类讨论，逐个击破即可。在解决过程中，我们的目标是让负数的运算能够成立，也即解决“操作数少一个”的问题，因此我们考虑“补上一个操作符0”使得式子能够运算。换言之，我们可以把"-1+2"变为"0-1+2"

思路已经给出，具体地解决那么就靠你的代码了！

Sample Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
char temp0_1[256] = {0};
for (int j = 0; j < len; j++){
    if (infix[i][j] == '('){ //处理括号后有减号的情况
      for (int s = t + 1; s < len; s++){
           if (infix[i][s] == '-'){ 
               for (int k = t + 1; k < len; k++){
                    temp0_1[k] = infix[i][k];//复制到temp0_1
               }
               for (int k = t + 1; k < len; k++){
                    infix[i][k + 1] = temp0_1[k];//将数据后移，空出第一个位置
               }
               infix[i][t + 1] = '0';			 //补0
               break;                    
                }
            }
    }

3. 变量处理

恭喜你！你已经能够成功计算简单的数学算式了！然而接下来你还需要处理变量。变量可能出现在等式左边或者右边，并且具有不同的含义，因此我们需要对变量进行一些定义。

Lab4给出了用数组的方式进行定义，其本质上是三组信息：

1
2
3
int variables[20]				//1.变量编号
char var_names[20]			//2.变量名称
double var_values[20]		//3.变量值

然而我们发现，这三组信息分别有着三个不同的数据类型，之后调用与处理的时候绝对会让你抓狂。To make your life easier, 我们引入另一种数据类型：

结构体 struct

结构体struct

如果你有一定编程基础，struct可以类比为其他语言中的class，或者是Matlab中的cell。结构体的优点在于可以容纳各种类型的数据，将某一个数据的各种不同类型的信息组合在一起形成一个整体的“结构”。看下面的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct Student{  
    char name[50];  		//姓名  
    int num;  			//学号  
    char sex;  			//性别  
    double score;  	//成绩  
};

我们一般这样调用：
int main(){
  struct Student David;
  David.num = 114514;
  printf("num:%d\n",David.num);
  return 0;
}

这样我们就定义好了Student的结构，我们可以非常轻松的调用struct中国的各种类型的数据。这种定义方式虽然没有问题，在中文互联网十分常见，但是每当我们要调用的时候就要struct XXX，非常麻烦不好看，因此我们普遍采用下面的方法调用：

1
2
3
4
5
6
7
8
9
10
11
typedef struct
{
	char name[50];
	int num;
	char sex[5];
	double score;
}Students;

int main(){
  Students David; //不需要在前面写struct了，简洁清楚.
}

所以很自然的，我们可以定义struct Variables来实现我们对变量的操作：

Sample Code

1
2
3
4
5
6
7
8
9
10
11
typedef struct
{
    char name[120];
    double value;
} variables
  
int main(){
  Variables variables[20]; 				//结构体可以组成一个数组
  variables[0].name = "abc";			//第一个variables结构体的name是abc
  varibales[0].value = 114.514;		//第一个variables结构体的value是114.514
}

结构体的其他操作可以参考视频：https://youtu.be/dqa0KMSMx2w

等号左边的变量

对于一个等式，等号左边的变量应该是被赋值的变量，并且这个变量的值可以在之后被调用。我们首先需要将等式左边的变量名存储到结构体name中，最后把算好的值返回给结构体中的value。在计算时，还需要识别等式右边的变量并找出他对应的值。

对于等号左边的变量，我们可以非常容易的把他作为字符串提取出来然后写入variables.name，你可能需要用到这个函数：

1
sprintf([写入的目标], [被写入的内容], "abc"); //"abc"告诉计算机写入的格式。

具体语法请自行搜索。

最后我们将计算得到的结果赋值给他就好了！

1
variables[i].value = [FinalAnswer];

等号右边的变量

显然，我们需要识别右边的变量并获得其对应的数值，然后返回给用于计算的double_RPE，然而这个过程看似简单，实则困难重重，请做好debug的心理准备。

要实现识别的操作，我们需要对2.3.3中的代码进行升级

Sample Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
if ((char_RPE[x] >= '0' && char_RPE[x] <= '9') || (char_RPE[x] == '.') || (char_RPE[x] >= 'a' && char_RPE[x] <= 'z')){
    temp[m] = char_RPE[x];
    m = m + 1;
    helper[l] = 1;
}
//变量的识别与转化（难点）由于temp中可能因为各种原因而没有元素导致之后strcmp失效，所以采取temp赋值和空字符判断
int a = 0;
int var_position;
for (int t = 0; t < i; t++){
     if (strcmp(temp, variable[t].var_name) == 0)
         a = a + 1;//变量判断
         var_position = t;
     if (strcmp(temp, variable[t].var_name) != 0)
         continue;
}

if (a >= 1)   
      double_RPE[y] = variable[var_position].var_value;
      y = y + 1;
//找到了之前的变量 采用之前存储的数据

if (a == 0)
      double_RPE[y] = strtod(temp, NULL);
      y = y + 1;
 //没找到 一定是数字（如果是新变量则不合法）

我们使用strcmp函数进行字符串的比较，用来查找右边变量对应的数值。注意，改代码直接复制不可能运行，你需要理解每一步后自己仿照这敲出来！

如果你发现结果完全不符合预期，强烈建议你使用printf来观察计算机到底在算写什么。难点在于后面四个if的条件应该怎么写。

Sample Code

1
2
printf("temp:%s		variable:%s\n",temp,variable[t].varname);
printf("True of Flase: %d\n", a);

终章

如果你勤于动脑，勤于动手打代码，勇于运行调试，那么到这里你应该能基本上有个比较漂亮的输出了。虽然很有可能你的结果还有错误，你的joj还告诉你runtime error，但你先别急，仔细检查你的while循环、if语句判断条件、你的top值，通过printf来观察计算机的行为并且找出错误！这一定非常煎熬，但是只要be patient，就一定可以找出对应的错误。

这里直接给出JOJ的测试点：

Sample Test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//盗取JOJ测试点的方法
上传一个程序，实现将"commands.txt"打印下来即可；
Then you can get:
a = 1 + 1
b= 10^(-2)
c =(0 /a+ 0 / 1+ 0/3 + 0/a + b * 2.5)* b^(-2)
d=a^( a^  2) /(4*8)
e   =-8+ (6+c)^1+3.04/(3.04^(a*d)* d)
a=    b*c + d - e + e^(b^(-1) / 50)
f = (2.5^( -2) -(-23.2)/(5.8)^(b^0) - 0.16)^(a ^ 0+b ^ 0+e ^ 0)
a = (((200*b)^2)^(1+f^(e^0/3)/2)*60/2+1)*3+10624/f^0.5
tenlengthv=-3.2+(8-2^2) + 1^100/((2^0.5)* (4^0.25)) + (-0.25)+ 1 - 0.6 / 0.4 + 16^ (1/0.25/16)
result1234=((((((a-7081)))))-(((( ((b^(-2)))))))*(((( (((1))))))-((((((0)))) )))/(((((-1)^2))) * ((((-2)^2))) ))
ans = result1234 * b + tenlengthv

如果这些测试点能够通过，最后加上分号的功能即可！（真的很简单！）

最后，祝福你能够在ddl前顺利Accepted！