表达式求值 | Yancey's Blog 个人经验分享

数据结构

学习记录

发布日期: 2023-09-10

文章字数: 1.6k

阅读时长: 6 分

阅读次数:

学习目标

掌握手算正则表达式转后缀表达式、前缀表达式

理解计算的过程并能写出相应的代码

增加表达式求值的功能

为什么需要前/ 后缀表达式？

后缀表达式可以去除原式中的括号，不需要括号就可以知道运算的优先级，便于计算机理解运算。

a+b*(c+d*e) 原表达式

a b c d e * + * + 后缀表达式

如何变换？手算

首先找出优先级较高的运算符，将其依次标号，依次将运算符移到右侧的操作数后，熟练后可以不加括号直接转换。

如何变换？机算

从左往右依次扫描：

1.遇到操作数
- 全部压入操作数栈；
- 结束条件是遇到括号或者运算符

2.遇到运算符

2.1 遇到 + -
- 当前运算符栈为空则直接输出
- 当前运算符栈不为空入栈

2.2 遇到 * /

 当前运算符栈为空则直接输出

 不为空则将运算符栈弹出，直到栈空或者遇到(

2.3 (

不为空则入栈

)

     弹出所有运算符直到遇到(

中缀转后缀表达式代码实现

void ExpreesionValue(char str[], char dest[]) {
    /**
     * @brief 求后缀表达式
     * @note
     * a*b+(c*d-e)
     * 1*2+3+3*4
     * 12*3+34*+
     * 1.遇到操作数
     *      全部压入操作数栈；
     *      结束条件是遇到括号或者运算符
     * 2.遇到运算符
     *      2.1 遇到+ -
     *          当前运算符栈为空则直接输出
     *          当前运算符栈不为空入栈
     *      2.2 遇到* /
     *          当前运算符栈为空则直接输出
     *          不为空则将运算符栈弹出，直到栈空或者遇到(
     *      2.3 (
     *          不为空则入栈
     *          )
     *          弹出所有运算符直到遇到(
     */
    SqStack S;
    InitStack(S, 20);
    char e;
    int i = 0;
    int j = 0;
    
    while (str[i] != '\0') {
        if (Isdigit(str[i])) {
            // 将所有操作数输出并添加空格
            dest[j++] = str[i++];
            while (Isdigit(str[i])) {
                dest[j++] = str[i++];
            }
            dest[j++] = ' ';

        } else {
            // 进行判空操作，如果为空或为'('直接入栈
            if (Empty(S) || str[i] == '(') {
                Push(S, str[i++]);
            } else if (str[i] == ')') {
                //如果遇到')'，在遇到'('前进行弹栈输出，最后将'('进行弹栈。
                while (S.data[S.top] != '(') {
                    Pop(S, dest[j++]);
                }
                char temps;
                Pop(S, temps);
                i++;
            } else {
                // 如果栈顶元素 >= 当前符号优先级，则弹栈输出，最后将该符号入栈
                while (priority(str[i]) <= priority(S.data[S.top])) {
                    Pop(S, dest[j++]);
                    if (Empty(S)) {
                        break;
                    }
                }
                Push(S, str[i++]);
            }
        }
    }
    // 将栈清空输出
    while (!Empty(S)) {
        Pop(S, dest[j++]);
    }
    dest[j] = '\0';
}

中缀表达式转前缀表达式代码实现

void ExpreesionValue(char str[], char dest[]) {
    /**
     * 前缀表达式
     * a+b*(c+d*e)
     * +a*b+c*de
     *
     * 从右往左扫描
     *      1.栈为空或遇')' 直接入栈
     *      2.遇到操作数直接输出
     *      3.遇到'(' 将栈内的元素弹栈输出，直到遇到')' ,并将')'弹出
     *      4.如果栈顶元素 >= 当前元素的优先级，则弹栈输出，最后将该符号入栈。
     *      5.将栈内元素清空，并在最后置入'\0'
     */

    SqStack S;
    InitStack(S, 20);
    char e;
    int j = 0;
    int length = strlen(str);
    int i = length - 1;
    while (i >= 0) {
        if (Isdigit(str[i])) {
            dest[j++] = str[i--];
            while (Isdigit(str[i])) {
                dest[j++] = str[i--];
            }
            dest[j++] = ' ';
        } else {
            if (Empty(S) || str[i] == ')') {
                Push(S, str[i--]);
            } else if (str[i] == '(') {
                while (S.data[S.top] != ')') {
                    Pop(S, dest[j++]);
                }
                char temps;
                Pop(S, temps);
                i++;
            } else {
                while (priority(S.data[S.top]) >= priority(str[i])) {
                    Pop(S, dest[j++]);
                    if (Empty(S)) {
                        break;
                    }
                }
                Push(S, str[i--]);
            }
        }
    }
    while (!Empty(S)) {
        Pop(S, dest[j++]);
    }
    dest[j] = '\0';
}

中缀转前缀表达式、后缀表达式的对比：

扫描顺序不同，后缀表达式是从左往右扫描。前缀表达式需要先计算中缀表达式长度从右往左扫描。
对括号的处理不同
- 后缀表达式对 ‘(‘ 及空进行直接入栈的操作，而前缀表达式则是对 ‘)’直接进行入栈的操作。
- 对另一半匹配的括号处理方式相同。
对运算符的处理相同，都是根据运算符的优先级决定是否出栈：栈顶元素 >= 当前元素的优先级则需要出栈，再将该运算符入栈、
前缀表达式输出到dest数组后，因为和存储是相反的，输出最终的前缀表达式结果时需要逆向输出结果。

表达式求值

思想：表达式求值需要构建两个栈，分别存储运算符和操作数

扫描后缀表达式时，从左往右读取。

扫描到操作数将其转换为int类型后进行入栈操作，
扫描到运算符时判断其运算类型，并从操作数栈中取出两个操作数进行运算，并将结果重新放回操作数栈
最后将操作数栈的结果输出即可

代码实现

int CaculateExpress(char str[]) {
    OqStack S1; //操作数栈
    S1.capacity = 20;
    S1.data = (int *)malloc(sizeof(int) * S1.capacity);
    S1.top = -1;
    SqStack S2; //符号栈
    InitStack(S2, 20);

    int left, right, i, j;
    char ch;
    int result = 0;
    while (str[i] != '\0') {
        int value = 0;
        if (Isdigit(str[i])) {
            while (str[i] != ' ') {
                value = value * 10 + str[i++] - '0';
            }
            Push(S1, value);
            while (str[i] == ' ') {
                i++;
            }

        } else if (Ismul(str[i]) || Issum(str[i])) {
            char sign = str[i];
            Pop(S1, right);
            Pop(S1, left);

            if (sign == '+') {
                value = left + right;
            } else if (sign == '-') {
                value = left - right;
            } else if (sign == '*') {
                value = left * right;
            } else {
                if (right == 0) {
                    printf("Error");
                    return -1;
                }
                value = left / right;
            }
            i++;
            Push(S1, value);
        }
        
    }
    if (S1.top != -1) {
        result = S1.data[S1.top--];
        return S1.top == -1 ? result : -1;
    }
}