浙大版《数据结构（第2版）》题目集习题3.11 表达式转换 (25分)

一、题目描述

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。

输入格式:
输入在一行中给出不含空格的中缀表达式，可包含+、-、*、\以及左右括号()，表达式不超过20个字符。

输出格式:
在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。

输入样例:
2+3*(7-4)+8/4

输出样例:
2 3 7 4 - * + 8 4 / +

二、解题思路

根据操作符op的优先级来进行栈的变化，运算符在栈内的优先级和栈外的优先级不同，icp(in coming priority)是栈外优先，isp(in stackpriority)是栈内优先。运算符在进栈前的优先级为icp，进栈后为isp。

我们在表达式后面加上符号#，表示表达式结束
采用双指针法，切割字符串，得到操作数和操作符

• 如果当前左指针的值为数字
  • 那么就采用双指针，找到其后第一个不是运算符的位置（主要是考虑了小数点的情况）
  • 因为当前找到的部分是操作数而不是操作符，直接加入结果串
  • 将左右指针中间的那部分子串加入结果串（而不是cout，减少I/O次数，加快运行速度）
• 否则，当左指针的值为运算符时
  • 如果这个运算符是+或-
    • 如果当前左指针在Index = 0的位置
      • 说明第一个操作数是带正负号的，再次采用双指针法切割出这个操作数，注意如果是负号的话就在前面加上负号，然后直接跳过本轮循环
    • 如果当前左指针不在Index = 0的位置
      • 如果isp[stk.top()] < icp[tmp]，那么直接进栈
      • 否则，从栈顶开始校验，一直退栈输出，直到找到isp[stk.top()] > icp[tmp]不成立的位置，此时退出时isp[stk.top()] <= icp[tmp]
      • 如果此时isp[stk.top()] == icp[tmp]，那么说明优先级相同，那么就是(为栈顶这种情况，退栈不输出
      • 否则说明isp[stk.top()] < icp[tmp]，将这个操作数压栈
• 切割字符串完成后，栈内操作符并没有全部退栈完成，那么挨个退栈，直到栈空
• 输出结果串

三、解题代码

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
using namespace std;
class Convert
{
private:
    static unordered_map<char, int> icp, isp;
    stack<char> stk;
    string src;
    string sln;
public:
    explicit Convert(const string &str)
    {
        src = str;
        stk.push('#');
    }
    void Solution();
};
unordered_map<char, int> Convert::icp{{'#', 0}, {'(', 6}, {')', 1}, {'*', 4}, {'/', 4}, {'+', 2}, {'-', 2}};
unordered_map<char, int> Convert::isp{{'#', 0}, {'(', 1}, {')', 6}, {'*', 5}, {'/', 5}, {'+', 3}, {'-', 3}};

void Convert::Solution()
{
    int left = 0, right = 0;
    auto len = src.size();
    for (; left < len; left++)	//双指针法切割字符串
    {
        if (isdigit(src[left]))	//没有正负号的情况进行切割
        {
            for (right = left; right < len && icp.find(src.at(right)) == icp.end(); right++)
                ;
            sln += src.substr(left, right - left);
            sln += " ";
            left = right - 1;
        }
        else
        {
            auto tmp = src.at(left);
            if (tmp == '-' || tmp == '+')
            {
            	//如果开头就是负号，没什么可说的
            	//或者该操作符前一个位置还是操作符，但是它前面那个操作符不是')'的话，说明它一定为正负号
                if (!left || (src.at(left - 1) != ')' && icp.find(src.at(left - 1)) != icp.end()))
                {
                    if (tmp == '-')
                        sln += tmp;
                    for (right = ++left; right < len && icp.find(src.at(right)) == icp.end(); right++)
                        ;
                    sln += src.substr(left, right - left);
                    sln += " ";
                    left = right - 1;
                    continue;
                }
            }
            if (isp[stk.top()] < icp[tmp])
                stk.push(tmp);
            else// if (isp[stk.top()] > icp[tmp])
            {//必须要把if (isp[stk.top()] > icp[tmp])注释掉，否则无法准确识别正负号，无法通过测试点
                while (isp[stk.top()] > icp[tmp])
                {
                    sln += stk.top();
                    sln += " ";
                    stk.pop();
                }
                isp[stk.top()] >= icp[tmp] ? stk.pop() : stk.push(tmp);
            }
        }
    }
    while (stk.size() > 1)//切割完成后排空栈
    {
        sln += stk.top();
        sln += " ";
        stk.pop();
    }
    sln = sln.substr(0, sln.size() - 1);//去掉结果串结尾的' '
    cout << sln << endl;
}
int main()
{
    string str;
    cin >> str;
    auto it = new Convert(str);
    it->Solution();
    delete it;
    it = nullptr;
    return 0;
}

四、运行结果