C++实现中缀表达式转化为后缀表达式详解

C++实现中缀表达式转化为后缀表达式详解

中缀表达式是人类一般使用的计算方式，而计算机更习惯于使用后缀表达式进行计算。因此，将中缀表达式转化为后缀表达式是很有必要的。下面就是C++实现中缀表达式转化为后缀表达式的攻略：

步骤一：定义运算符优先级

在将中缀表达式转化为后缀表达式时，需要对每一个运算符赋予优先级，以便在转化过程中确定运算的先后顺序。通常来说，加减法的优先级低于乘除法，则可以将加减法定义为优先级1，乘除法定义为优先级2。

既然要定义运算符的优先级，可以考虑使用map来实现。例如，在C++中可以用以下代码定义优先级：

map<char, int> priority = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};//运算符优先级

步骤二：将中缀表达式转化为后缀表达式

将中缀表达式转化为后缀表达式需要使用到栈。从左到右依次扫描中缀表达式，扫描到的是数字时直接将其加入到后缀表达式中，扫描到的是运算符时则需要将其与栈顶元素进行比较。

如果栈顶运算符的优先级大于当前元素运算符的优先级，则弹出栈顶元素并加入到后缀表达式中，如此重复，直至栈顶元素的优先级小于当前元素运算符的优先级或者栈已经为空，则将当前元素压入到栈中；如果栈顶元素的优先级小于或等于当前元素运算符的优先级，则直接将当前元素压入到栈中。

上述过程可以使用以下代码实现：

vector<string> infix2postfix(string& s) {
    stack<char> stk;
    vector<string> ans;
    for(int i=0; i<s.size(); ) {
        if(isdigit(s[i])) {
            string num;
            while(i<s.size() && isdigit(s[i])) num+=s[i], i++;
            ans.push_back(num);
        } else if(s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/') {
            while(!stk.empty() && priority[stk.top()] >= priority[s[i]]) {
                ans.push_back(string()+stk.top());
                stk.pop();
            }
            stk.push(s[i]), i++;
        } else i++;
    }
    while(!stk.empty()) ans.push_back(string()+stk.top()), stk.pop();
    return ans;
}

示例一：

输入：3+4*2/(1-5)^2^3

输出：3 4 2 * 1 5 - 2 3 ^ ^ / +

示例二：

输入：(10+2)4/((5-3)2)

输出：10 2 + 4 * 5 3 - 2 * /

总结

将中缀表达式转化为后缀表达式可以使用栈来实现，需要将运算符定义优先级以便在转化过程中确定运算的先后顺序，同时还需要注意扫描到的是数字还是运算符。