前、后与中——表达式求值

AI摘要
加载中...
摘要由AI自动生成，仅供参考！

记录一下最近的练习程序与做法，加深记忆，也当个教程吧，毕竟赠人玫瑰手留余香(bushi

如果你不知道这些表达式分别指什么东西，可以百度一下，这里不再赘述。

后缀表达式

这个应该是最常见的了，下面讲一下实现。

首先，还是定义函数废话：

1
2
3
int main() {
	//...
}

然后，进行文件读取，可以用freopen()，不过我这里用的是fopen()：

1
2
3
4
5
6
7
8
9
10
FILE* stream = fopen("input.txt", "r");
stack<double> nums;
while(true) {
	char tstr[100]; //temp
	fscanf(stream, "%s", tstr);
	if(feof(stream)) break;
	string input = tstr;

	//...
}

解释一下上面的程序：

  • stack<double> nums 这个栈后面会用到，这里先不用管
  • fscanf()和scanf()用法一样，唯一的区别是fscanf()用于读取文件流中的信息而非输入流
  • feof()中的参数为文件流，用于判断是否读到结尾，读到则返回真

很显然，这段程序用于分别读入每一段字符，那么接下来便是判断输入了。

代码如下：

1
2
3
4
5
6
7
8
9
10
while(true) {
	//...

	if(isdigit(input[0])) {
		nums.push(atof(input.c_cstr()));
	}
	else {
		//...
	}
}

如果输入为整数，则进入数字栈，否则开始计算。

这里使用了isdigit()函数，输入为char类型，用于判断参数是否在'0'与'9'之间。

计算过程很简单，弹出两个数字栈中的数，根据运算符计算即可：

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
//...
else {
	double y = nums.top();
	nums.pop();
	double x = nums.top();
	nums.pop();

	double temp;
	switch(input[0]) {
		case '+':
			temp = x + y;
			break;

		case '-':
			temp = x - y;
			break;

		case '*':
			temp = x * y;
			break;

		case '/':
			temp = x / y;
			break;
	}

	nums.push(temp);
}

尤其要注意减法与除法的操作数与被操作数顺序，毕竟它们可没有交换律。

此时已经计算完成，结果作为栈中唯一的元素处在栈顶，直接输出即可：

1
2
3
4
fclose(stream); //关文件是一个好习惯
cout<<nums.top()<<endl;

return 0;

大概就是这样。

完整代码还是放一下：

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;

inline bool is_num(string str) {
	if(str[0] >= '0' && str[0] <= '9') return true;
	else return false;
}

int main() {
	FILE* stream = fopen("input.txt", "r");
	stack<double> nums;
	while(true) {
		char tstr[100];
		fscanf(stream, "%s", tstr);
		if(feof(stream)) break;
		string input = tstr;
		if(is_num(input)) {
			nums.push(atof(input.c_str()));
		}
		else {
			double y = nums.top();
			nums.pop();
			double x = nums.top();
			nums.pop();
			double temp;
			switch(input[0]) {
				case '+':
					temp = x + y;
					break;

				case '-':
					temp = x - y;
					break;

				case '*':
					temp = x * y;
					break;

				case '/':
					temp = x / y;
					break;
			}
			nums.push(temp);
		}
	}
	fclose(stream);
	cout<<nums.top()<<endl;
	
	return 0;
}

输入样例：

1
1 2 + 3 -

输出样例：

1
0

前缀表达式

细心一点就能发现，它与后缀表达式几乎一样，只是顺序不同。

没错，这正是因为前、后、中缀表达式分别为表达式树的先序、后续与中序遍历。

利用这个性质，将后缀表达式的顺序稍稍更改即可得到前缀表达式求值的程序：

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;

inline bool is_num(string str) {
    if(str[0] >= '0' && str[0] <= '9') return true;
    else return false;
}

int main(){
    FILE* stream = fopen("input.txt", "r");
    
    stack<double> nums;
    vector<string> input; //存储读取数据
    while(true) {
        char tstr[100];
        fscanf(stream, "%s", tstr);
        if(feof(stream)) break;
        input.push_back(string(tstr));
    }
    
    for(int i = input.size() - 1;i >= 0;i--) { //倒序读取
        if(is_num(input[i])) {
            nums.push(atof(input[i].c_str()));
        }
        else {
            double x = nums.top();
            nums.pop();
            double y = nums.top();
            nums.pop();
            
            double temp;
            switch(input[i][0]) {
                case '+':
                    temp = x + y;
                    break;
                
                case '-':
                    temp = x - y;
                    break;
                
                case '*':
                    temp = x * y;
                    break;
                
                case '/':
                    temp = x / y;
                    break;
            }
            
            nums.push(temp);
        }
    }
    
    fclose(stream);
    cout<<nums.top()<<endl;
    
    return 0;
}

改成倒序读取即可。

输入样例：

1
- + 1 2 3

输出样例：

1
0

中缀表达式

我们最常用的表达式，处理起来却是最复杂的，因为现在需要考虑优先级与括号了。

这里有几种方法：

递归

首先，定义函数用于取多项式的因子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int factor() {
    int res = 0;
    char c = cin.peek();
    if(c == '(') {
        cin.get();
        res = expression();
        cin.get();
    }
    else {
        while(isdigit(c)) {
            res = 10 * res + c - '0';
            cin.get();
            c = cin.peek();
        }
    }
    return res;
}

先定义结果为0，然后判断输入。若为括号，则将其内容视为新表达式，交由马上要定义的expression()函数计算。否则，按位取出输入中的数即可。

顺带一提，这些代码中的cin.get()与cin.peek()尤其重要，切勿移动位置或轻易替换。至于原因，自己模拟想一下吧。

然后，计算单项式的值，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int term() {
    int res = factor();
    while(true) {
        char mark = cin.peek();
        if(mark == '*' || mark == '/') {
            cin.get();
            int v = factor();
            if(mark == '*') res *= v;
            else res /= v;
        }
        else break;
    }
    return res;
}

先用factor()函数读入因子，然后循环判断该单项式是否读完。若未读完（即该因子与下一个因子间仍用乘号或除号连接）则取下一个因子并计算，否则返回该单项式的值即可。并且很显然，这样的写法就代表输入的表达式中不应当含有任何空格，也只支持整数运算（要浮点数自己改我不干了）。

最后是整个表达式，与计算单项式基本一样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int expression() {
    int res = term();
    while(true) {
        char mark = cin.peek();
        if(mark == '+' || mark == '-') {
            cin.get();
            int v = term();
            if(mark == '+') res += v;
            else res -= v;
        }
        else break;
    }
    return res;
}

读入单项式再计算，直到该表达式计算完毕（即mark取到)或EOF）

主函数其实已经一目了然了，重定向输入再调用expression()即可，就不写了。

输入样例：

1
(28/7)/2+(8-9)

输出样例：

1
1

栈

这里又分为两种方案：

转为后/前缀表达式再计算

这里的重点是转换的过程，逻辑整体如下（中缀->后缀）：

  • 输入若为数字，直接放入输出表达式中。若为符号：
    • 如果符号栈为空，则放入符号栈中
    • 如果符号栈栈顶元素优先级大于等于该符号，则出栈栈顶符号放入表达式，若此时栈顶符号优先级大于等于该符号，则重复以上流程直至小于，而后入栈该符号
    • 如果符号栈栈顶元素优先级小于该符号，该符号入栈
    • 如果该符号为左括号，直接入栈
    • 如果该符号为右括号，则依次出栈符号栈栈顶元素放入表达式中，直至左括号。最后抛弃左括号与右括号
  • 若输入完毕，符号栈中仍有符号，则依次出栈放入表达式

代码如下（转为后缀表达式）：

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
map<char, int> markl;

markl['+'] = 0;
markl['-'] = 0;
markl['*'] = 1;
markl['/'] = 1;

FILE* stream = fopen("input.txt", "r");

stack<char> marks;
vector<string> expression;
while(true) {
    char tstr[100];
    fscanf(stream, "%s", tstr);
    if(feof(stream)) break;
    string input = tstr;
    
    if(isdigit(input[0])) {
        expression.push_back(input);
    }
    else if(input[0] == '(') {
        marks.push('(');
    }
    else if(input[0] == ')') {
        while(true) {
            if(marks.top() == '(') {
                marks.pop();
                break;
            }
            char t[2] = {marks.top(), '\0'};
            expression.push_back(string(t));
            marks.pop();
        }
    }
    else {
        if(marks.empty() || marks.top() == '(') {
            marks.push(input[0]);
        }
        else if(markl[input[0]] <= markl[marks.top()]) {
	        while(!marks.empty() && markl[temp[0]] <= markl[marks.top()]) {
	            char t[2] = {marks.top(), '\0'};
	            expression.push_back(string(t));
	            marks.pop();
	        }
	        marks.push(input[0]);
        }
        else {
            marks.push(input[0]);
        }
    }
}

while(!marks.empty()) {
	char t[2] = {marks.top(), '\0'};
	expression.push_back(string(t));
	marks.pop();
}

和上面的逻辑完全一样，唯一要注意的是这里使用了map，可以理解为字典。

然后只需要计算就行，代码就不放了。

前缀表达式的逻辑与代码可以自己想想。

输入输出样例同下面。

直接计算

逻辑和转换本身是一样的，只不过没有了表达式向量，而是直接计算后放入数字栈。

即将所有的对于expression的操作改为计算即可：

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <bits/stdc++.h>
using namespace std;

double calc(char mark, double x, double y) {
    double temp = 0;
    switch(mark) {
        case '+':
            temp = x + y;
            break;
        
        case '-':
            temp = x - y;
            break;
        
        case '*':
            temp = x * y;
            break;
        
        case '/':
            temp = x / y;
            break;
    }

    return temp;
}

int main() {
    FILE* stream = fopen("input.txt", "r");

    map<char, int> markl;
    markl['+'] = 0;
    markl['-'] = 0;
    markl['*'] = 1;
    markl['/'] = 1;

    stack<char> marks;
    stack<double> nums;
    while(true) {
        char tstr[100];
        fscanf(stream, "%s", tstr);
        if(feof(stream)) break;
        string temp = tstr;

        if(isdigit(temp[0])) {
            nums.push(atof(temp.c_str()));
        }
        else if(temp[0] == '(') {
            marks.push('(');
        }
        else if(temp[0] == ')') {
            while(true) {
                if(marks.top() == '(') {
                    marks.pop();
                    break;
                }

                double y = nums.top();
                nums.pop();
                double x = nums.top();
                nums.pop();
                nums.push(calc(marks.top(), x, y));

                marks.pop();
            }
        }
        else if(marks.empty() || marks.top() == '(') {
            marks.push(temp[0]);
        }
        else if(markl[temp[0]] <= markl[marks.top()]) {
	        while(!marks.empty() && markl[temp[0]] <= markl[marks.top()]) {
	            double y = nums.top();
	            nums.pop();
	            double x = nums.top();
	            nums.pop();
	            nums.push(calc(marks.top(), x, y));
	
	            marks.pop();
	        }
            marks.push(temp[0]);
        }
        else {
            marks.push(temp[0]);
        }
    }

    while(!marks.empty()) {
        double y = nums.top();
        nums.pop();
        double x = nums.top();
        nums.pop();
        nums.push(calc(marks.top(), x, y));

        marks.pop();
    }

	fclose(stream);
	
    cout<<nums.top()<<endl;
    return 0;
}

输入样例：

1
( 28 / 7 ) / 2 + ( 8 - 9 )

输出样例：

1
1

收工！

题外话

这篇大概是我最长的纯原创技术类博文了。。。。。。

好累QAQ

下次再见啦！886！

2023.04.03更新

让ChatGPT改了一个支持浮点数的递归版本：

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;

void print_tab(int);
void print_log(string, int);
void print_log(string, int, double);
double expression(int);
double term(int);
double factor(int);

int main() {
    freopen("input.txt", "r", stdin);
    cout << expression(0) << endl;
    return 0;
}

void print_tab(int deep) {
    for(int i = 0;i < deep;i++) {
        cout << "\t";
    }
    return;
}

void print_log(string name, int deep) {
    print_tab(deep);
    cout << name << " {" << endl;
    return;
}

void print_log(string name, int deep, double res) {
    print_tab(deep);
    cout << "} -> res =" << res << endl;
    return;
}

double expression(int deep) {
    print_log("expression", deep);

    double res = term(deep + 1);
    while(true) {
        char mark = cin.peek();             //get
        if(mark == '+' || mark == '-') {
            cin.get();                      //skip
            double v = term(deep + 1);
            if(mark == '+') res += v;
            else res -= v;
        }
        else break;
    }

    print_log("expression", deep, res);

    return res;
}

double term(int deep) {
    print_log("term", deep);

    double res = factor(deep + 1);
    while(true) {
        char mark = cin.peek();             //get
        if(mark == '*' || mark == '/') {
            cin.get();                      //skip
            double v = factor(deep + 1);
            if(mark == '*') res *= v;
            else res /= v;
        }
        else break;
    }

    print_log("term", deep, res);
    
    return res;
}

double factor(int deep) {
    print_log("factor", deep);

    double res = 0;
    double base = 1.0;
    char c = cin.peek();                    //get
    if(c == '(') {
        cin.get();                          //skip
        res = expression(deep + 1);
        cin.get();                          //skip
    }
    else {
        while(isdigit(c) || c == '.') {     // == GET A NUMBER ==
            if(c == '.') {
                cin.get();                  //skip the '.'
                c = cin.peek();             //get the next character
                while(isdigit(c)) {         //collect digits for the decimal part
                    res = res + (c - '0') * (base /= 10.0);
                    cin.get();
                    c = cin.peek();
                }
                break;
            }
            res = res * 10 + c - '0';       //get num
            cin.get();                      //skip
            c = cin.peek();                 //get
        }
    }

    print_tab(deep + 1);
    cout << "get_num();" << endl;
    print_log("factor", deep, res);

    return res;
}

神

编程
#计算机 #编程 #cpp #算法
前、后与中——表达式求值
https://www.ordchaos.com/posts/c9c6cb4f/
作者
序炁
发布于
2023年4月2日
更新于
2023年4月3日
许可协议