Infix to Postfix с использованием стека и очереди: не удалось получить доступ к памяти C++

Question

Я пытаюсь взять строку с расширением и изменить ее на постфикс.

Я считаю, что большая часть кода должна работать, однако есть проблема с «Невозможно прочитать память», когда очередь Queue :: enqueue (char, int) называется программой, не может читать «переднюю» или «заднюю», если Я изменяю iString в test_driver.cpp. Я получаю ту же ошибку, но на Stack :: empty(). Я считаю, что это проблема с ассоциативностью между классами.

В последней попытке каната сделанные классы друзья друг друга, но я не уверен, что это правильный подход. Я добавил все файлы ниже. Любая помощь будет принята с благодарностью.

* test_driver.cpp 

*******************************************************************************/ 
#include <iostream> 
#include "Stack.h" 
#include "Queue.h" 
#include "EqConverter.h" 
using namespace std; 

int main() { 
    string inputString, resultString; 
    EqConverter* testQueue= new EqConverter; 

    inputString = "2+3"; 

    testQueue->convert_to_pf(inputString); 
    resultString = testQueue->return_exp(); 

    cout << resultString; 


cin.get(); 
    delete testQueue; 

    return 0; 


    /*Queue* testQueue = new Queue; 

    for (int i = 0; i < 100; i++) 
    { 
     testQueue->enqueue(i, i); 
    } 

    for (int i = 0; i < 100; i++) 
    { 
     cout<<testQueue->dequeue()->data<<endl; 

    } 

    delete testQueue;*/ 

    cin.get(); 
/*************************************************/ 

EqConverter.cpp

#include <iostream> 
#include <string> 
#include "Stack.h" 
#include "Queue.h" 
#include "EqConverter.h" 

using namespace std; 


EqConverter::EqConverter() 
{ 
    Stack*op_stack = new Stack; 
    Queue*exp_queue = new Queue; 
} 

EqConverter::~EqConverter() 
{ 
    delete op_stack; 
    delete exp_queue; 
} 

int EqConverter::convert_to_pf(string iString) 
{ 
    // Function to verify whether a character is english letter or numeric digit. 
    // We are assuming in this solution that operand will be a single character 

    //Begin Actual converting from infix to postfix// 
    for (int i = 0; i < iString.length(); i++) 
    { 
     if (IsOperator(iString[i])) 
     { 
      while (!op_stack->empty() && op_stack->top()->data != '(' && HasHigherPrecedence(op_stack->top()->data, iString[i])) 
      { 
       exp_queue->enqueue(op_stack->top()); 
       op_stack->pop(); 
      } 
      op_stack->push(iString[i], GetOperatorWeight(iString[i])); 
     } 
     // Else if character is an operand 
     else if (IsOperand(iString[i])) 
     { 
      exp_queue->enqueue(iString[i], GetOperatorWeight(iString[i])); 
     } 

     else if (iString[i] == '(' || iString[i] == '[') 
     { 
      op_stack->push(iString[i], GetOperatorWeight(iString[i])); 
     } 

     else if (iString[i] == ')') 
     { 
      while (!op_stack->empty() && op_stack->top()->data != '(') 
      { 
       exp_queue->enqueue(op_stack->top()); 
       op_stack->pop(); 
      } 
      op_stack->pop(); 
     } 
    } 

    while (!op_stack->empty()) 
    { 
     exp_queue->enqueue(op_stack->top()); 
     op_stack->pop(); 
    } 


    return 0; 
} 

bool EqConverter::IsOperand(char C) 
{ 
    if (C >= '0' && C <= '9') return true; 
    if (C >= 'a' && C <= 'z') return true; 
    if (C >= 'A' && C <= 'Z') return true; 
    return false; 
} 

// Function to verify whether a character is operator symbol or not. 
bool EqConverter::IsOperator(char C) 
{ 
    if (C == '+' || C == '-' || C == '*' || C == '/' || C == '$' || C == '[' || C == '%') 
     return true; 

    return false; 
} 

// Function to verify whether an operator is right associative or not. 
int EqConverter::IsRightAssociative(char op) 
{ 
    if (op == '$') return true; 
    return false; 
} 


// Function to get weight of an operator. An operator with higher weight will have higher precedence. 
int EqConverter::GetOperatorWeight(char op) 
{ 
    int weight = -1; 
    switch (op) 
    { 
    case '(': 
    case '[': 
     weight = 0; 
     break; 
    case '+': 
    case '-': 
     weight = 1; 
     break; 
    case '*': 
    case '/': 
    case '%': 
     weight = 2; 
     break; 
    case '$': 
     weight = 3; 
    } 
    return weight; 
} 

// Function to perform an operation and return output. 
int EqConverter::HasHigherPrecedence(char op1, char op2) 
{ 
    int op1Weight = GetOperatorWeight(op1); 
    int op2Weight = GetOperatorWeight(op2); 

    // If operators have equal precedence, return true if they are left associative. 
    // return false, if right associative. 
    // if operator is left-associative, left one should be given priority. 
    if (op1Weight == op2Weight) 
    { 
     if (IsRightAssociative(op1)) 
      return false; 

     else 
      return true; 
    } 
    return op1Weight > op2Weight ? true : false; 
} 

string EqConverter::return_exp() 
{ 
    string pString; 


    while (exp_queue->dequeue() != 0) 
    {  
     pString.push_back(exp_queue->dequeue()->data); 
    } 

    return pString; 
} 


} 

Queue.cpp

#include"Node.h" 
#include"Queue.h" 


using namespace std; 

Queue::Queue() 
{ 
    front = new Node; 
    front = 0; 

    rear = new Node; 
    rear = 0; 
} 

Queue::~Queue() 
{ 
    destroy_Queue(); 
    delete front; 
    delete rear; 
} 

void Queue::destroy_Queue() 
{ 
    Node* temp; 

    while (front!=0) 
    { 
     temp = front; 
     front = front->link; 
     delete temp; 

    } 
} 

void Queue::enqueue(char info, int order) 
{ 
    Node* temp; 
    temp = new Node; 

    temp->data = info; 
    temp->precedence = order; 

    if (front == 0) 
    { 
     front = temp; 
     rear = temp; 
    } 
    else 
    { 
     rear->link = temp; 
     rear = rear->link; 
    } 
} 

void Queue::enqueue(Node* newNode) 
{ 
    newNode = new Node; 

    if (front == 0) 
    { 
     front = newNode; 
     rear = newNode; 
    } 
    else 
    { 
     rear->link = newNode; 
     rear = rear->link; 
    }  
} 

Node* Queue::dequeue() 
{ 
    Node* temp; 

    if (front != 0) 
    { 
     temp = front; 
     front = front->link; 
     return temp; 
    } 
    else 
     return 0; 
} 

Stack.cpp

#include"Node.h" 
#include"Stack.h" 

using namespace std; 

Stack::Stack() 
{ 
    tos = 0; 
} 

Stack::~Stack() 
{ 
    destroy_Stack(); 
    delete tos; 
} 

void Stack::destroy_Stack() 
{ 
    Node* temp;   //Pointer to delete the node 

    while (tos != 0) //delete the tos while it is not pointing to NULL 
    { 
     temp = tos;  //assign temp to "tos" so its link can be broken 
     tos = tos->link;//advance "tos" to the node below it in the stack 

     delete temp; //Delete temp which pointed to the node of the previous "tos" 

    } 
} 


Node* Stack::top() const 
{ 
    if (tos==0) 
     return 0; 
    else 
     return tos; 
} 

void Stack::push(char info, int rank) 
{ 
    Node* newNode; 
    newNode= new Node; //create a new node to store incoming data 
    newNode->data = info;  //storing the incoming char into the data of the new node 
    newNode->precedence = rank; //synonym to store incoming numerical precdence into the new node 
    newNode->link= tos; //link newNode to old "tos" 

    tos = newNode; //Now that the link is created we can assign newNode as "tos" 
} 

void Stack::push(Node* newTop) 
{ 
    newTop->link = tos; //link new top node to old "tos" 
    tos = newTop;  //Now that the link is created we can assign newTop as "tos" 
} 

Node* Stack::pop() 
{ 
    if (tos == 0) 
     return 0; 

    Node* temp; 
    temp= new Node; //Creates a temp node to store current "tos" 
    temp = tos;    //pointer to keep track of "tos" 
    tos = tos->link;  //Advances "tos" to what was stored under it 

    return temp;   //Returns what "tos" was before advancing it 
} 

bool Stack::empty() 
{ 
    if (tos == 0) 
     return true; 
    else 
     return false; 
} 

И соответствующие Header файлы

EqConverter.h

#ifndef EQCONVERTER_H 
#define EQCONVERTER_H 

#include<string> 

using namespace std; 

class EqConverter { 
    private: 

    Stack *op_stack; 
    Queue *exp_queue; 

    //My functions for easier implementation 
    bool IsOperand(char); 
    bool IsOperator(char); 
    int IsRightAssociative(char); 
    int GetOperatorWeight(char); 
    int HasHigherPrecedence(char, char); 

    public: 
    EqConverter(); // creates an Stack and Queue object using dynamic memory 
    ~EqConverter(); // cleans up the Stack and Queue objects 

    /* convert_to_pf *********************************************************** 
    * iteratively traverses the string passed in and performs the steps of the 
    * conversion algorithm using the Stack and Queue; the conversion algorithm 
    * is provided in the assignment statement. You will need to provide a 
    * variable for the string parameter 
    ***************************************************************************/ 
    int convert_to_pf(string); 


    // returns a string of the converted postfix expression stored in exp_queue 
    string return_exp(); 


    friend class Stack; 
    friend class Queue; 
}; 

#endif 

Queue.h

/******************************************************************************* 
* Queue.h 

*******************************************************************************/ 
#ifndef QUEUE_H 
#define QUEUE_H 

#include <iostream> 
#include "Node.h" 

class Queue { 
    private: 
    Node* front; // pointer to the front of the queue 
    Node* rear; // pointer to the rear of the queue 


    public: 
    Queue(); // initializes front and rear to a null pointer 
    ~Queue(); // deletes all nodes in the queue; may call destroy_Queue 

    /* The enqueue method ****************************************************** 
    * enqueue(char, int): creates a new node and places it at the rear of the 
    *  queue, you will need to provide variables for the char/int parameters 
    * 
    * enqueue(Node*): adds the passed in Node argument to the rear of the queue; 
    *  you will need to provide a variable for the Node* parameter 
    ***************************************************************************/  
    void enqueue(char, int); 
    void enqueue(Node*); 

    /* The pop and top methods ************************************************* 
    * dequeue(): disconnects and returns the node at the front of the queue. 
    *  This method also updates front to point to the new front. If the 
    *  queue is empty, it should return the null pointer.  
    ***************************************************************************/ 
    Node* dequeue(); 

    // iteratively traverse the linked list that makes up the queue and deletes 
    // each node 
    void destroy_Queue(); 

    friend class EqConverter; 
}; 

#endif 

Stack.h

/******************************************************************************* 
* Stack.h 

*******************************************************************************/ 
#ifndef STACK_H 
#define STACK_H 

#include "Node.h" 

class Stack { 
    private: 
    Node *tos; // the pointer to the Top Of Stack (TOS) 

    public: 
    Stack(); // does nothing more than just initialize tos to a null pointer 
    ~Stack(); // deletes all nodes in the stack; may call destroy_Stack 

    /* The push method ********************************************************* 
    * push(char, int): creates a new node and places it on the TOS, you will 
    *  need to provide variables for the char and int parameters 
    * 
    * push(Node*): adds the passed in Node argument to the TOS; you will need 
    *  to provide a variable for the Node* parameter 
    ***************************************************************************/ 
    void push(char, int); 
    void push(Node*); 


    /* The pop and top methods ************************************************* 
    * pop(): disconnects and returns the node at the TOS; a pointer is returned. 
    *  This method also updates tos to point to the new TOS. If the stack is 
    *  empty, it should return the null pointer. 
    * 
    * top(): returns a pointer to the Node at the TOS. If the stack is empty, 
    *  it should return the null pointer. 
    ***************************************************************************/ 
    Node* pop(); 
    Node* top() const; 

    // iteratively traverse the linked list that makes up the stack and deletes 
    // each node 
    void destroy_Stack(); 

    bool empty(); 

    friend class EqConverter; 
}; 

#endif 

node.h

/******************************************************************************* 
* Node.h 

*******************************************************************************/ 
#ifndef NODE_H 
#define NODE_H 

struct Node { 
    char data; 
    int precedence; 
    Node *link; 

    // this overloaded operator uses a reference to a pointer variable 
    bool operator < (const Node *&rhs) const { 
    return this->precedence < rhs->precedence; 
    } 
}; 

#endif 

Answer 1

Я использовал Valgrind с вашей программой и это показало у меня проблемы с вашим кодом немедленно:

==15835== Use of uninitialised value of size 8 
==15835== at 0x401ABC: Queue::enqueue(char, int) (in /home/A.Romanek/tmp/programming/so-1/main) 
==15835== by 0x4013C6: EqConverter::convert_to_pf(std::string) (in /home/A.Romanek/tmp/programming/so-1/main) 
==15835== by 0x400E9E: main (in /home/A.Romanek/tmp/programming/so-1/main) 
==15835== 
==15835== Invalid read of size 8 
==15835== at 0x401ABC: Queue::enqueue(char, int) (in /home/A.Romanek/tmp/programming/so-1/main) 
==15835== by 0x4013C6: EqConverter::convert_to_pf(std::string) (in /home/A.Romanek/tmp/programming/so-1/main) 
==15835== by 0x400E9E: main (in /home/A.Romanek/tmp/programming/so-1/main) 
==15835== Address 0x0 is not stack'd, malloc'd or (recently) free'd 
==15835== 
==15835== 
==15835== Process terminating with default action of signal 11 (SIGSEGV) 
==15835== Access not within mapped region at address 0x0 
==15835== at 0x401ABC: Queue::enqueue(char, int) (in /home/A.Romanek/tmp/programming/so-1/main) 
==15835== by 0x4013C6: EqConverter::convert_to_pf(std::string) (in /home/A.Romanek/tmp/programming/so-1/main) 
==15835== by 0x400E9E: main (in /home/A.Romanek/tmp/programming/so-1/main) 

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

Тем не менее, я бы рекомендовал использовать <queue> и <stack> от STL. Это должно помочь вам.