Проблема синтаксического анализатора математических выражений 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 (code=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

Итак, вы помещаете операцию в стек. Однако позже вы снимаете его со стека и помещаете его в очередь, прежде чем поместить следующую цифру в очередь.

Это определенно неправильный порядок, но, если вы изучите код, это не просто небольшой фрагмент, содержащий две строки в неправильном порядке (это было бы слишком просто).

Код, который выполняет эту передачу из стека в очередь, является окончательным while зациклиться main() который после каждого отдельного символа переносит все элементы из стека в очередь, эффективно делая ваш стек лишним.

Вот где вы должны искать, но я дам вам подсказку. Вы не хотите передавать стек в очередь после каждого символа, только для тех, которые содержат числа.

Вполне возможно, что после того, как вы решите эту проблему, могут возникнуть другие проблемы, но этот метод (отладка вывода каждый раз, когда вы делаете что-то важное) должен быть в состоянии дать вам достаточно информации, чтобы исправить все, что приходит.