算法 | 中缀表达式转后缀表达式并计算结果（利用栈）

1.手动实现中缀转后缀

2.代码实现中缀转后缀并计算表达式结果

为了简化问题，假设算术运算符仅由加、减、乘、除4种运算符和左、右括号组成。

step1: 声明栈结构

#include 
#include 
using namespace std;

#define MaxSize 100
template <class DataType>
struct SeqStack
{
    DataType data[MaxSize];
    DataType *top;
};

step2: 定义函数TranslateInfixExp实现中缀表达式转后缀表达式

/* 中缀表达式转后缀表达式 */
void TranslateInfixExp(string exp, string &result)
{
    if (exp.empty())
        return;
    // step1: 定义操作符栈并初始化栈
    struct SeqStack<char> opStack;
    opStack.top = opStack.data;

    // step2: 遍历中缀表达式
    char cur;
    for (int i = 0; i < exp.size(); i++)
    {
        cur = exp[i];
        switch (cur)
        {
        // 遇到 '(' ，入栈
        case '(':
            *(opStack.top++) = cur;
            break;
        // 遇到 ')' ，依次将栈中的运算符出栈并加入后缀表达式中，直至栈顶元素为 '(' ，'(' 出栈
        case ')':
            while (*(opStack.top - 1) != '(')
            {
                result.push_back(*(--opStack.top));
                result.push_back(' ');
            }
            opStack.top--;
            break;
        // 遇到 '+' 或 '-'，依次将优先级不低于所读运算符的栈顶元素出栈并加入后缀表达式，然后将所读运算符入栈
        case '+':
        case '-':
            while ((opStack.top != opStack.data) && *(opStack.top - 1) != '(')
            {
                result.push_back(*(--opStack.top));
                result.push_back(' ');
            }
            *(opStack.top++) = cur;
            break;
        // 遇到 '*' 或 '/' ，依次将优先级不低于所读运算符的栈顶元素出栈并加入后缀表达式，然后将所读运算符入栈
        case '*':
        case '/':
            while ((opStack.top != opStack.data) && (*(opStack.top - 1) == '*') || (*(opStack.top - 1) == '/'))
            {
                result.push_back(*(--opStack.top));
                result.push_back(' ');
            }
            *(opStack.top++) = cur;
            break;
        // 遇到数字字符，直接入栈
        default:
            while (cur >= '0' && cur <= '9')
            {
                result.push_back(cur);
                cur = exp[++i];
            }
            result.push_back(' ');
            i--; // 回退至后续首个尚未进行优先级判断的操作字符
            break;
        }
    }
    // step3: 将栈内剩余元素依次出栈
    while (opStack.top != opStack.data)
    {
        result.push_back(*(--opStack.top));
        result.push_back(' ');
    }
    return;
}

注意：

1. 在将中缀表达式转后缀表达式过程中，每输出一个数字字符，需要在其后补一个空格（与其他相邻数字字符隔开），否则一连串数字字符放在一起无法区分是一个数字还是两个数字。
2. 遇到数字字符入栈时，若当前运算项位数>1时，需要在当前数字字符入栈后后移一位并重复入栈（代码中switch的default段代码），并在运算项入栈完毕之后需要将索引i回退至后续首个尚未进行优先级判断的运算符上（即非数字字符）。

step3: 定义函数CaculatePostFixExp实现后缀表达式结果计算

/* 计算后缀表达式结果 */
float CaculatePostFixExp(string exp)
{
    float result = 0;
    if (exp.empty())
    {
        cout << "The expression is wrong!\n";
        exit(-1);
    }

    // step1 : 定义一个数据字符栈，并初始化
    struct SeqStack<float> numStack;
    numStack.top = numStack.data;

    // step2 : 遍历后缀表达式
    char cur;
    for(int i=0; isize(); i++)
    {
        cur = exp[i];
        if (cur >= '0' && cur <= '9') // 若当前字符为数字字符
        {
            float value = 0;
            while (cur != ' ')
            {
                value = value * 10 + cur - '0';
                cur = exp[++i];
            }
            *(numStack.top++) = value;
        }
        else if(cur != ' ') // 若当前字符是运算符（空格直接忽略）
        {
            float num1 = *(--numStack.top);
            float num2 = *(--numStack.top);
            switch (cur)
            {
            case '+':
                *(numStack.top++) = num2 + num1;
                break;
            case '-':
                *(numStack.top++) = num2 - num1;
                break;
            case '*':
                *(numStack.top++) = num2 * num1;
                break;
            case '/':
                *(numStack.top++) = num2 / num1;
                break;
            default:
                break;
            }
        }
    }
    // step3 : 栈中最终元素出栈，即为所求表达式的值 
    if (numStack.top != numStack.data)
    {
        result = *(--numStack.top);
        return result;
    }
    else
    {
        cout << "The expression is wrong!\n";
        exit(-1);
    }
}

注意：

若当前字符为运算符且为减号'-'时，先出栈的为减数，后出栈的为被减数；对于除法'/'也一样。

step4: main函数调用

int main()
{
    string infixExp;   // 存储用户输入的中缀表达式
    string postfixExp; // 存储转换后的后缀表达式
    float result;     // 存储后缀表达式计算机结果
    cout << "Please enter an infix expression:\n";
    cin >> infixExp; // 6+(7-1)*3+10/2
    cout << "The infix expression is:  " << infixExp << endl;
    TranslateInfixExp(infixExp, postfixExp);
    cout << "The postfix expression is:  " << postfixExp << endl;
    result = CaculatePostFixExp(postfixExp);
    cout << "The postfix expression calculation result is:  " << result << endl;
    return 0;
}

输出：

Please enter an infix expression:
6+(7-1)*3+10/2
The infix expression is:  6+(7-1)*3+10/2
The postfix expression is:  6 7 1 - 3 * + 10 2 / +
The postfix expression calculation result is:  29