一、题目描述

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

输入格式:
输入在一行中给出不含空格的中缀表达式，可包含+、-、*、\以及左右括号()，表达式不超过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;
}

计算器

#include <iostream>
#include <stack>
#include <string>
#include <cstdlib>
#include <unordered_map>
#include <iomanip>
using namespace std;
class Convert
{
   
private:
    static unordered_map<char, int> icp, isp;
    stack<char> stk;
    string src;
    string sln;
    void Back();
    double calc(double tmp1, char oper, double tmp2);
public:
    explicit Convert(const string &str)
    {
   
        src = str;
        stk.push('#');
    }
    double eval();
};
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::Back()
{
   
    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;
}

double Convert::calc(double first, char oper, double second){
   
    double ans;
    if(oper == '+')    ans =  first + second;
    else if(oper == '-')    ans = first - second;
    else if(oper == '*')    ans = first * second;
    else if(oper == '/')    ans = first / second;
    else{
   
        cerr << "Invalid operator!" << endl;
        exit(1);
    }
    return ans;
}

double Convert::eval(){
   
    Back();
    stack<double> num;
    size_t left = 0, right = 0;
    auto len = sln.size();
    for(; left < len; left++){
   
        for(right = left; right < len && sln.at(right) != ' '; right++);
        if(right - left == 1){
   
            if(icp.find(sln.at(left)) != icp.end()){
   
                auto oper = sln.at(left);
                auto second = num.top();
                num.pop();
                auto first = num.top();
                num.pop();
                num.push(calc(first, oper, second));
            }
            else    num.push(sln.at(left) - '0');
        }
        else    num.push(atof(sln.substr(left, right - left).c_str()));
        left = right;
    }
    return num.top();
}
int main()
{
   
    string str;
    cin >> str;
    auto it = new Convert(str);
    cout << fixed << setprecision(10) << it->eval() << endl;
    delete it;
    it = nullptr;
    return 0;
}

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

一、题目描述

二、解题思路

三、解题代码

计算器

四、运行结果