Я пытаюсь взять строку инфиксного выражения и изменить ее на постфикс.
Я считаю, что большая часть кода должна работать, однако есть проблема с «Невозможно прочитать память», когда вызывается 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;
}
}
Очередь.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;
}
И соответствующие заголовочные файлы
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
*******************************************************************************/
#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
*******************************************************************************/
#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
Узел.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
Queue
имеет утечку памяти. Дальше не читал, потому что инопланетяне. - person Captain Obvlious   schedule 27.10.2014stack
, так иqueue
, поэтому нет необходимости изобретать велосипед. Их использование поможет вам сосредоточиться на работе. - person Adam Romanek   schedule 27.10.2014I am trying to take a string of an infixed expression and change it to postfix.
Похоже, вы пытаетесь реализовать всевозможные вспомогательные структуры данных вместо конечной цели. Если вам нужен стек, естьstd::stack
— вам нужна очередь, естьstd::queue
— вам нужен преобразователь инфикса в постфикс, теперь это то, что вы должны кодировать, используя вышеупомянутые типы. - person PaulMcKenzie   schedule 27.10.2014