Alex_McAvoy

想要成为渔夫的猎手

栈与表达式的计算

发表于 分类于 ， ，
本文字数： 5.5k 阅读时长 ≈ 5 分钟

【表达式类型】

一个表达式一般由操作数、运算符、界限符三个部分组成，根据运算符的位置，表达式可分为以下三类：

  • 中缀表达式（算术表达式）：运算符在两运算数中间，界限符反映了计算的先后顺序
  • 前缀表达式（波兰式）：无界限符，运算符在前，操作数在后
  • 后缀表达式（逆波兰式）：无界限符，运算符在后，操作数在前
中缀 前缀 后缀
a + b + a b a b +
a + b - c - + a b c a b + c -
a + b - c * d - + a b *c d a b + c d * -

注：缀指的是运算符的位置

【后缀表达式的计算】

在计算后缀表达式时，从前向后扫描，遇到运算符时，让运算符前的两个操作数执行相应运算，合并为一个操作数，并将运算符与其前的两个操作数替换为这个新得到的操作数，继续扫描，重复上述步骤，直到处理完成

根据上述处理步骤，可以发现其运算规则符合栈后入先出的特性，故而可采用以下算法：

  1. 从前向后扫描表达式的下一元素，直到所有元素处理完成，栈中最后剩余的元素即为结果
  2. 若扫描到操作数，令操作数入栈，转向步骤 1
  3. 若扫描到运算符，连续出栈两次，此时先出栈的是右操作数，执行相应运算，运算结果入栈，转向步骤 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
void postfix_of_cal() { //后缀表达式计算
    char postfix[N];
    stack<int> S;

    cin.get(postfix,N);
    int len = strlen(postfix);
    int left_op, right_op;
    for (int i = 0; i < len; i++) { //从前向后遍历
        if (postfix[i] == '+') {
            right_op = S.top(); S.pop(); //右操作数先出栈
            left_op = S.top(); S.pop();
            S.push(left_op + right_op);
        } 
        else if (postfix[i] == '-') {
            right_op = S.top(); S.pop(); //右操作数先出栈
            left_op = S.top(); S.pop();
            S.push(left_op - right_op);
        } 
        else if (postfix[i] == '*') {
            right_op = S.top(); S.pop(); //右操作数先出栈
            left_op = S.top(); S.pop();
            S.push(left_op * right_op);
        } 
        else if (postfix[i] == '/') {
            right_op = S.top(); S.pop(); //右操作数先出栈
            left_op = S.top(); S.pop();
            S.push(left_op / right_op);
        } 
        else {
            if (postfix[i] != ' ') {
                int temp = 0;
                while (postfix[i] != ' ') {
                    temp = temp * 10 + postfix[i] - '0';
                    i++;
                }
                S.push(temp);
            }
        }
    }
    printf("%d\n", S.top());
}

【前缀表达式的计算】

在计算前缀表达式时，从后向前扫描，遇到运算符时，让运算符后的两个操作数执行相应运算，合并为一个操作数，并将运算符与其后的两个操作数体会为这个新得到的操作数，继续扫描，重复上述步骤，直到处理完成

根据上述处理步骤，可以发现其运算规则符合栈后入先出的特性，故而可采用以下算法：

  1. 从后向前扫描表达式的下一元素，直到所有元素处理完成，栈中最后剩余的元素即为结果
  2. 若扫描到操作数，令操作数入栈，转向步骤 1
  3. 若扫描到运算符，连续出栈两次，此时先出栈的是左操作数，执行相应运算，运算结果入栈，转向步骤 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
void prefix_of_cal() {  //前缀表达式计算
    char prefix[N];
    stack<int> S;

    cin.get(prefix,N);
    int len = strlen(prefix);
    int left_op, right_op;
    for (int i = len - 1; i >= 0; i--) { //从后向前遍历
        if (prefix[i] == '+') {
            left_op = S.top(); S.pop(); //左操作数先出栈
            right_op = S.top(); S.pop();
            S.push(left_op + right_op);
        } 
        else if (prefix[i] == '-') {
            left_op = S.top(); S.pop(); //左操作数先出栈
            right_op = S.top(); S.pop();
            S.push(left_op - right_op);
        } 
        else if (prefix[i] == '*') {
            left_op = S.top(); S.pop(); //左操作数先出栈
            right_op = S.top(); S.pop();
            S.push(left_op * right_op);
        } 
        else if (prefix[i] == '/') {
            left_op = S.top(); S.pop(); //左操作数先出栈
            right_op = S.top(); S.pop();
            S.push(left_op / right_op);
        } 
        else {
            if (prefix[i] != ' ') {
                int num = 0;
                int pos = 0;
                while (prefix[i] != ' ') {
                    int temp = prefix[i] - '0';
                    temp *= pow(10, pos);
                    num += temp;
                    i--;
                    pos++;
                }
                S.push(num);
            }
        }
    }
    printf("%d\n", S.top());
}

【中缀表达式转后缀表达式】

由于中缀表达式的运算顺序难以界定，因此在遇到中缀表达式时，可将中缀表达式转换为后缀表达式，之后进行后缀计算

在将中缀表达式转换为后缀表达式时，由于运算顺序不唯一，因此对应的后缀表达式也不唯一，一般采取左优先原则，即左边的运算符只要能先计算，就先转换左边的

在转换时，采取如下算法：

  1. 初始化一个栈，用于保存暂时无法确定运算顺序的运算符
  2. 从前向后扫描，逐个处理字符，根据遇到的字符决定处理方式
    • 遇到操作数：直接加入后缀表达式
    • 遇到界限符：遇到 ( 直接入栈，遇到 ) 将栈中的操作符依次弹出加入后缀表达式，直到弹出 ( 为止
    • 遇到运算符：依次弹出栈中大于等于当前运算符优先级的所有运算符，加入后缀表达式，直到弹出 ( 为止，之后再将当前运算符入栈
  3. 扫描完毕后，将栈中剩余运算符依次弹出，加入后缀表达式
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
int getLevel(char x) { //算符优先级
    if (x == '+' || x == '-')
        return 1;
    if (x == '*' || x == '/')
        return 2;
    if (x == '^')
        return 3;
    return 0; // ( 与 ) 的优先级
}
void infix_to_postfix() { //中缀转后缀
    char infix[N];
    char postfix[N];
    stack<char> S;

    cin.get(infix,N);
    int len = strlen(infix);
    memset(postfix, '\0', sizeof(postfix));

    int pos = 0;
    for (int i = 0; i < len; i++) {
        if(infix[i] == ' ')
            continue;

        if (infix[i] == '(') // ( 入栈
            S.push(infix[i]);
        else if (infix[i] == ')') {
            while (!S.empty() && S.top() != '(') { //遇到 ( 为止
                postfix[pos++] = S.top();
                postfix[pos++] = ' ';
                S.pop();
            }
            S.pop(); // ( 出栈
        } 
        else if (infix[i] == '+' || infix[i] == '-' || infix[i] == '*' ||
                 infix[i] == '/' || infix[i] == '^') {
            
            //当前算符优先级小于等于栈中运算符优先级
            while (!S.empty() && getLevel(infix[i]) <= getLevel(S.top())) {
                char op = S.top();
                postfix[pos++] = op;
                postfix[pos++] = ' ';
                S.pop();
            }
        
            S.push(infix[i]); //当前操作符入栈
        } 
        else { //数字
            postfix[pos++] = infix[i];
            if (i + 1 == len || infix[i + 1] == ' ')
                postfix[pos++] = ' ';
        }
    }
    while (!S.empty()) { //栈中剩余算符出栈
        postfix[pos++] = S.top();
        postfix[pos++] = ' ';
        S.pop();
    }

    printf("%s\n", postfix);
}

【中缀表达式转前缀表达式】

由于中缀表达式的运算顺序难以界定，因此在遇到中缀表达式时，可将中缀表达式转换为前缀表达式，之后进行前缀计算

在将中缀表达式转换为前缀表达式时，由于运算顺序不唯一，因此对应的前缀表达式也不唯一，一般采取右优先原则，即右边的运算符只要能先计算，就先转换右边的

在转换时，采取如下算法：

  1. 初始化一个栈，用于保存暂时无法确定运算顺序的运算符
  2. 从前向后扫描，逐个处理字符，根据遇到的字符决定处理方式
    • 遇到操作数：直接加入表达式
    • 遇到界限符：遇到 ) 直接入栈，遇到 ( 将栈中的操作符依次弹出加入表达式，直到弹出 ) 为止
    • 遇到运算符：依次弹出栈中大于等于当前运算符优先级的所有运算符，加入表达式，直到弹出 ) 为止，之后再将当前运算符入栈
  3. 扫描完毕后，将栈中剩余运算符依次弹出，加入表达式
  4. 将表达式进行翻转，即得到前缀表达式
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
int getLevel(char x) { //算符优先级
    if (x == '+' || x == '-')
        return 1;
    if (x == '*' || x == '/')
        return 2;
    if (x == '^')
        return 3;
    return 0; // ( 与 ) 的优先级
}
void infix_to_prefix() { //中缀转前缀
    char infix[N];
    char prefix[N];
    stack<char> S;

    cin.get(infix,N);
    int len = strlen(infix);
    memset(prefix, '\0', sizeof(prefix));

    int pos = 0;
    for (int i = len - 1; i >= 0; i--) {
        if (infix[i] == ' ')
            continue;

        if (infix[i] == ')') // ) 入栈
            S.push(infix[i]);
        else if (infix[i] == '(') {
            while (!S.empty() && S.top() != ')') { //遇到 ) 为止
                prefix[pos++] = S.top();
                prefix[pos++] = ' ';
                S.pop();
            }
            S.pop(); // ) 出栈
        } 
        else if (infix[i] == '+' || infix[i] == '-' || infix[i] == '*' ||
                 infix[i] == '/' || infix[i] == '^') {
            
            //当前算符优先级小于等于栈中运算符优先级
            while (!S.empty() && getLevel(infix[i]) <= getLevel(S.top())) {
                char op = S.top();
                prefix[pos++] = op;
                prefix[pos++] = ' ';
                S.pop();
            }
        
            S.push(infix[i]); //当前操作符入栈
        } 
        else { //数字
            prefix[pos++] = infix[i];
            if (i == 0 || infix[i - 1] == ' ')
                prefix[pos++] = ' ';
        }
    }
    while (!S.empty()) {
        prefix[pos++] = S.top();
        prefix[pos++] = ' ';
        S.pop();
    }
    reverse(prefix, prefix + pos);

    printf("%s\n", prefix + 1);
}
感谢您对我的支持，让我继续努力分享有用的技术与知识点！