[C++知识库]C语言栈的应用——后缀表达式求值

算法思路

? 上次已经完成了由中缀表达式转后缀表达式的算法，而后缀表达式的优点就是可以从左至右直接读取，没有算数优先级的考量，所以直接进行运算即可。

? 该算法需要使用一个栈用来保存操作数，在读取到数字的时候，将数字压入栈中；如果读取到操作符，就弹出栈顶的两个元素，分别为op2和op1（先弹出来的元素为op2），将op1和op2与目前读取到的操作符进行计算，并将结果压回栈中。反复运行直到后缀表达式全部读取完成，此时栈中的结果即后缀表达式的结果。

具体过程

例后缀表达式12+3-45*2/+，定义一个栈num来保存数字，顺序读取后缀表达式。

1. 读取到数字1，将其压入栈中，此时num = ['1']
2. 读取到数字2，将其压入栈中，此时num = ['1','2']
3. 读取到操作符+，将栈顶的两个元素弹出，op2=2，op1=1，将op1+op2的结果压入栈中，此时num = ['3']
4. 读取到数字3，将其压入栈中，此时num = ['3','3']
5. 读取到操作符-，将栈顶的两个元素弹出，op2=3，op1=3，将op1-op2的结果压入栈中，此时num = ['0']
6. 读取到数字4，将其压入栈中，此时num = ['0','4']
7. 读取到数字5，将其压入栈中，此时num = ['0','4','5']
8. 读取到操作符*，将栈顶的两个元素弹出，op2=5，op1=4，将op1*op2的结果压入栈中，此时num = ['0','20']
9. 读取到数字2，将其压入栈中，此时num = ['0','20','2']
10. 读取到操作符/，将栈顶的两个元素弹出，op2=2，op1=20，将op1/op2的结果压入栈中，此时num = ['0','10']
11. 读取到操作符+，将栈顶的两个元素弹出，op2=10，op1=0，将op1+op2的结果压入栈中，此时num = ['10']
12. 后缀表达式读取完毕，此时栈num的内容即后缀表达式的结果。

代码实现

// 后缀表达式求值
void postfixEval()
{
    char postfixList[100] = {0};    // 使用char类型数组保存后缀表达式
    printf("请输入将要求值的后缀表达式:\n");
    scanf("%s", postfixList);
    getchar();
    int length;
    length = (int) strlen(postfixList);
    LiStack num;    // 定义栈num保存数字，并定义
    num = initStack();

    for (int i = 0; i < length; i++)
    {
        if (isdigit(postfixList[i]))
        {
            int nums = asciiToint(postfixList[i]);  // 因为在char类型中保存数字是ascii码类型，所以需要将其转义，具体函数在下方
            push(num, nums);    // 将数字压入栈中
        }
        else
        {
            int second = pop(num);
            int first = pop(num);
            push(num, domatch(first, postfixList[i], second));  // 调用domatch（定义在下方），将对应结果再次压入栈中
        }
    }
    printf("该表达式的值为%d\n", pop(num));
}

// 将ascii码转化为整形

int asciiToint(char ascii)
{
    // 因为在ascii码中，48表示0，49表示1……将ascii-'0'，就是将对应数字的ascii码减去48，结果就是十进制中的数字
    int i = ascii - '0';
    return i;
}

// 算数求值
int domatch(int op1, char op, int op2)  // 将char类型的运算符进行相应的运算
{
    int first = (int)op1, second = (int)op2;
    if (op == '*')
    {
        return first * second;
    }
    else if(op == '/')
    {
        return first / second;
    }
    else if (op == '+')
    {
        return first + second;
    }
    else
    {
        return first - second;
    }
}