C++ 数学表达式解析器问题

Question

#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include "NodeType.h"
using namespace std;

// Test if token is an operator
bool isOperator(char token);

int getPrecedence(char token);

bool comparePrecedence(char tokenA, char tokenB);


int main()
{

    stack<char> tokenStack;
    queue<char> tokenQueue;
    string expression= "", postfix= "";
    char x;
    cout<<"Please enter a mathematical expression: "<<endl;
    getline(cin, expression);
    cout<<expression.length()<<endl;
    for(int i = 0; i <= expression.length(); i++)
    {
        x = expression[i];
        if(isdigit(x))
        {
            tokenQueue.push(x);
        }
        if(isOperator(x))
        {
            while((!tokenStack.empty()) && (comparePrecedence(x, tokenStack.top() == true)))
            {
               char z = tokenStack.top();
               tokenQueue.push(z);
               tokenStack.pop();
            }
            tokenStack.push(x);
        }
        if(x == '(')
        {
            tokenStack.push(x);
        }
        if(x == ')')
        {
            while((!tokenStack.empty()) && (tokenStack.top() != '('))
            {
                char z = tokenStack.top();
                tokenQueue.push(z);
                tokenStack.pop();
            }
            tokenStack.pop();
        }
        while(!tokenStack.empty())
        {
            char z = tokenStack.top();
            tokenQueue.push(z);
            tokenStack.pop();
        }
    }

    return 0;
}

int getPrecedence(char token)
{
    if((token == '+') || (token == '-'))
    {
        return 1;
    }
    else if((token == '*') || (token == '/'))
    {
        return 2;
    }
    else if ((token == '(') || (token == ')'))
        return 0;
    else
        return 99;
}

// Test if token is an operator
bool isOperator(char token)
{
    return token == '+' || token == '-' ||
    token == '*' || token == '/';
}

bool comparePrecedence(char tokenA, char tokenB)
{
    if(getPrecedence(tokenA) < getPrecedence(tokenB))
        return true;
    else
        return false;
}

出于某种原因，我无法让我的代码正常工作。它总是抛出一个线程 1：EXC_BAD_ACCESS（代码=EXC_1386_GPFLT）错误。当我使用一个简单的字符串进行测试时，它也没有正确放置“+”号：(3+4)。队列应如下所示：34+ 但它包含 3+4。在我看来，“+”运算符永远不会被压入堆栈。谁能帮我看看我应该关注什么？

Answer 1

调试代码是一项值得学习的技能，我认为它应该成为学校课程中更更重要的部分。

例如，如果您修改代码以输出所有堆栈和队列操作：

int main()
{

    stack<char> tokenStack;
    queue<char> tokenQueue;
    string expression= "", postfix= "";
    char x;
    cout<<"Please enter a mathematical expression: "<<endl;
    getline(cin, expression);
    cout<<expression.length()<<endl;
    for(int i = 0; i <= expression.length(); i++)
    {
        x = expression[i];
        if(isdigit(x))
        {
            tokenQueue.push(x);
            cout << "qpush A " << x << '\n';
        }
        if(isOperator(x))
        {
            while((!tokenStack.empty()) && (comparePrecedence(x, tokenStack.top() == true)))
            {
               char z = tokenStack.top();
               tokenQueue.push(z);
               cout << "spop  G " << z << '\n';
               cout << "qpush B " << z << '\n';
               tokenStack.pop();
            }
            tokenStack.push(x);
            cout << "spush E " << x << '\n';
        }
        if(x == '(')
        {
            tokenStack.push(x);
            cout << "spush F " << x << '\n';
        }
        if(x == ')')
        {
            while((!tokenStack.empty()) && (tokenStack.top() != '('))
            {
                char z = tokenStack.top();
                tokenQueue.push(z);
                cout << "spop  H " << z << '\n';
                cout << "qpush C " << z << '\n';
                tokenStack.pop();
            }
            cout << "spop  I " << tokenStack.top() << '\n';
            tokenStack.pop();
        }
        while(!tokenStack.empty())
        {
            char z = tokenStack.top();
            tokenQueue.push(z);
            cout << "spop  J " << z << '\n';
            cout << "qpush D " << z << '\n';
            tokenStack.pop();
        }
    }

    return 0;
}

和运行它与一个简单的3+4，你会看到以下输出：

qpush A 3
spush E +
spop  J +
qpush D +
qpush A 4

所以你是将操作放在堆栈上。但是，您稍后将其从堆栈中取出并放入队列 ，然后 将下一个数字放入队列。

这绝对是错误的顺序，但是，如果您检查代码，它不仅仅是一个有两行顺序错误的小片段（那太容易了）。

执行从堆栈到队列传输的代码是 main() 中的最终 while 循环，其中 在每个字符之后， 传输所有项目从堆栈到队列，有效地使您的堆栈变得多余。

那是你应该寻找的地方，但我会给你一个线索。您不想在每个字符之后将堆栈传输到队列，仅针对那些涉及数字的字符。

在你解决那个问题之后可能还有其他问题，但是那个方法（每次你做一些重要的事情时调试输出）应该能够给你足够的信息来修复任何出现的问题。

C++ 数学表达式解析器问题

C++ Mathematical Expression Parser Issue

c++

infix-notation

shunting-yard