C++ Математическое выражение Parser Issue

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; 
} 

По какой-то причине я не могу заставить свой код работать правильно. Он всегда выдает ошибку Thread 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(), который после каждого символа, передает все элементы из стека в очередь, эффективно рендеринг ваш стек излишни.

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

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