我的逆波兰表达式输出为什么不对呢

Question

#哪位大佬帮我看看，我的逆波兰表达式输出为什么不对呢？

• 应该输出的是：10.5 4.5 + 3 - 12 2 5 + 3 - 2 / * - 5 5 1 4 * - * +
• 代码输出的是：10.5 4.5 + 3 - 12 2 5 + 3 - 2 / * 5 5 1 4 * - * + -
  有一个减号的顺序不对！
  主要看 toRPN()函数就好。

#include <iostream>
#include <string>
#include <stack>
#include <vector>

using std::cout;
using std::cin;
using std::endl;
using std::stack;
using std::string;
using std::vector;

void toRPN(string usrInput, int inputLen, vector<string>* rpnArray);
bool isDigit(char chInStr);
bool isDigit(string str);
double calculator(vector<string>* rpnArray);
double opt(double num2, double num1, string optr);
int optrOrder(char optr);

int main()
{
    cout << "请输入算式：" << endl;
    cout << "- 输入：";
    string usrInput = "10.5+4.5-3-12*((2+5-3)/2)+5*(5-1*4)";
    cout << usrInput << endl;
    //std::getline(cin, usrInput);
    int inputLen = (int)usrInput.length();
    vector<string> rpnArray;
    toRPN(usrInput, inputLen, &rpnArray);
    cout << "- 结果：" << calculator(&rpnArray) << endl;
    return 0;
}

//将表达式转换为逆波兰表达式
void toRPN(string usrInput, int inputLen, vector<string>* rpnArray)
{
    stack<char> Operator;
    //中缀转后缀
    int i = 0;
    while (i < inputLen)
    {
        //处理空格
        if (usrInput[i] == ' ')
        {
            i++;
            continue;
        }
        //处理操作数
        if (isDigit(usrInput[i]))
        {
            string numStr;
            while (i < inputLen && (isDigit(usrInput[i]) || usrInput[i] == '.'))
            {
                numStr += usrInput[i++];
            }
            rpnArray->push_back(numStr);
            continue;
        }
        //处理左括号
        if (usrInput[i] == '(')
        {
            Operator.push(usrInput[i]);
            i++;
        }
        //处理右括号
        else if (usrInput[i] == ')')
        {
            while (!Operator.empty() && Operator.top() != '(')
            {
                rpnArray->push_back(string(1, Operator.top()));
                Operator.pop();
            }
            if (!Operator.empty())
            {
                Operator.pop();
            }
            i++;
        }
        //处理四则运算符
        else if (optrOrder(usrInput[i]) > 0)
        {
            if (!Operator.empty() && Operator.top() != '(' &&
                optrOrder(Operator.top()) >= optrOrder(usrInput[i]))
            {
                rpnArray->push_back(string(1, Operator.top()));
                Operator.pop();
            }
            Operator.push(usrInput[i]);
            i++;
        }
        //处理无效字符
        else
        {
            i++;
            continue;
        }
    }
    //处理剩下的内容

    //输出测试
    while (!Operator.empty())
    {
        rpnArray->push_back(string(1, Operator.top()));
        Operator.pop();
    }
    for (int i = 0; i < (int)rpnArray->size(); i++)
    {
        cout << (*rpnArray)[i] << " ";
    }
    cout << endl;
}

//判读字符是否为数字
bool isDigit(char chInStr)
{
    if ((chInStr >= '0' && chInStr <= '9') || chInStr == '.')
    {
        return true;
    }
    return false;
}
//判读字符串是否为数字
bool isDigit(string str)
{
    bool judge;
    for (int i = 0; i < (int)str.length(); i++)
    {
        if ((str[i] >= '0' && str[i] <= '9') || str[i] == '.')
        {
            judge = true;
        }
        else
        {
            judge = false;
        }
    }
    return judge;
}

//获取运算结果
double calculator(vector<string>* rpnArray)
{
    stack<double> Number;
    int arrLen = (int)rpnArray->size();
    double left;
    double right;
    double result;
    for (int i = 0; i < arrLen; i++)
    {
        if (isDigit((*rpnArray)[i]))
        {
            Number.push(stod((*rpnArray)[i]));
        }
        else
        {
            right = Number.top();
            Number.pop();
            left = Number.top();
            Number.pop();
            result = opt(left, right, (*rpnArray)[i]);
            Number.push(result);
        }
    }
    return result;
}

//计算运算符两侧数字
double opt(double left, double right, string optr)
{
    if (optr == "+")
    {
        return left + right;
    }
    else if (optr == "-")
    {
        return left - right;
    }
    else if (optr == "*")
    {
        return left * right;
    }
    else
    {
        return left / right;
    }
}

//获取优先级
int optrOrder(char optr)
{
    if (optr == '+' || optr == '-')
    {
        return 1;
    }
    if (optr == '*' || optr == '/')
    {
        return 2;
    }
    return 0;
}

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

首先，我们注意到中缀表达式转换为逆波兰表达式的算法中可能存在问题。在处理四则运算符时，我们应该按照运算符的优先级进行操作，但是看起来我们的代码可能存在顺序问题。 通过观察代码，我们发现在处理四则运算符时，如果遇到当前操作符优先级比栈顶操作符优先级高的情况，我们应该直接将当前操作符压入栈中。然而，当前代码中我们在执行这部分逻辑时有一个判断条件可能存在问题，导致顺序不正确。 为了解决这个问题，我们可以修改代码中处理四则运算符的部分逻辑，确保按照优先级正确压入操作符到栈中。 下面是一个修改后的代码示例：

int optrOrder(char optr) {
    if (optr == '+' || optr == '-') {
        return 1;
    } else if (optr == '*' || optr == '/') {
        return 2;
    } else {
        return 0;
    }
}
void toRPN(string usrInput, int inputLen, vector<string>* rpnArray) {
    stack<char> Operator;
    int i = 0;
    while (i < inputLen) {
        ... // 省略其他部分代码
        // 处理四则运算符
        else if (optrOrder(usrInput[i]) > 0) {
            while (!Operator.empty() && Operator.top() != '(' &&
                   optrOrder(Operator.top()) >= optrOrder(usrInput[i])) {
                rpnArray->push_back(string(1, Operator.top()));
                Operator.pop();
            }
            Operator.push(usrInput[i]);
            i++;
        }
        ... // 省略其他部分代码
    }
    // 处理剩下的内容
    while (!Operator.empty()) {
        rpnArray->push_back(string(1, Operator.top()));
        Operator.pop();
    }
    for (int i = 0; i < (int)rpnArray->size(); i++) {
        cout << (*rpnArray)[i] << " ";
    }
    cout << endl;
}

通过修改代码中的四则运算符处理逻辑，按照优先级正确处理操作符的顺序，可以得到正确的逆波兰表达式输出。您可以尝试运行这个更新后的代码并检查输出结果是否符合预期。