バイナリーツリーの再帰関数についての質問です。以下のテストプログラムを作ったりました。コンパイルはうまくいきますが、やりたいことができていません。これをコンパイルすると ()
が想定よりも多く表示されています。どのようにしたら ((A+B)*(C-D))
と (((A-B)+C)*(D/E))
のように表示できますか。
ptrがnullptrに到達したときにoutputの最後の文字を消すことができれば解決できるように思えるのですが、最後の文字の消し方もわかりません。この問題を解ける方よろしくお願いします。
main.cpp
int main(int argc, const char * argv[]) {
std::cout << "Testing Base Parse Tree" << std::endl << std::endl;
std::string expression1 = "AB+CD-*";
std::string expression2 = "AB-C+DE/*";
ParseTree ptree1(expression1);
std::cout << "Input is AB+CD-* " << std::endl;
std::cout << "In Order should be ((A+B)*(C-D)) and is " << ptree1.inOrder() << std::endl;
ParseTree ptree2(expression2);
std::cout << "Input is AB-C+DE/* " << std::endl;
std::cout << "In Order output should be (((A-B)+C)*(D/E)) and is" << ptree2.inOrder() << std::endl;
std::cout << "Done with Parse Tree test" << std::endl << std::endl;
return 0;
}
ParseTree.cpp
#include "ParseTree.h"
#include <string>
Stack::Stack(){head = nullptr;}
Stack::~Stack()
{
while(head != nullptr)
{
pop();
}
}
void Stack::push(Node* value)
{
Link* temp = new Link(value);
temp->setNext(head);
head = temp;
}
void Stack::pop()
{
Link* temp = head;
head = head->getNext();
delete temp;
}
Node* Stack::top()
{
return head->getValue();
}
bool Stack::empty()
{
if(head == nullptr)
{
return true;
}
return false;
}
ParseTree::ParseTree(string expression)
{
if(expression == "")
{
root = nullptr;
}
else {
root = doParse(expression);
}
}
ParseTree::~ParseTree()
{
//call recDelete
recDelete(root);
}
//delete nodes recursively
void ParseTree::recDelete(Node* ptr)
{
if(ptr != nullptr)
{
recDelete(ptr->getLeft());
recDelete(ptr->getRight());
delete ptr;
}
}
Node* ParseTree::doParse(string expression)
{
Stack theStack;
for (int i = 0; i < expression.length(); i++) {
char letter = expression[i];
if (isOperand(letter) == true) {
theStack.push(new Node(letter));
} else {
Node *temp = new Node(letter);
temp->setRight(theStack.top());
theStack.pop();
temp->setLeft(theStack.top());
theStack.pop();
theStack.push(temp);
}
}
return theStack.top();
}
bool ParseTree::isOperand(char letter)
{
if(letter == '+' || letter == '-' || letter == '*' || letter == '/' || letter == '(' || letter == ')')
{
return false;
}
return true;
}
bool ParseTree::isOperator(char letter)
{
if(letter == '+' || letter == '-' || letter == '*' || letter == '/')
{
return true;
}
return false;
}
string ParseTree::inOrder()
{
return recInOrder(root);
}
string ParseTree::recInOrder(Node* ptr)
{
string output = "";
if(ptr == nullptr)
{
return output;
}
output = output + "(" + recInOrder(ptr->getLeft());
output = output + ptr->getValue();
output = output + recInOrder(ptr->getRight()) + ")";
return output;
}
ParseTree.h
#include <iostream>
using std::string;
const char LPAREN = '(';
const char RPAREN = ')';
class Node{
private:
char value;
Node* left;
Node* right;
public:
//constructor
Node(char value){left = right = nullptr; this->value = value;}
//setter
void setLeft(Node* left){this->left = left;}
void setRight(Node* right){this->right = right;}
//getter
Node* getLeft(){return left;}
Node* getRight(){return right;}
char getValue() {return value;}
};
class Link{
private:
Node* value;
Link* next;
public:
Link(Node* value, Link* next = nullptr){this->value = value; this->next = next;}
void setNext(Link* next){this->next = next;}
Link* getNext(){return next;}
Node* getValue(){return value;}
};
class Stack{
private:
Link* head;
public:
Stack();
~Stack();
void push(Node* value);
void pop();
Node* top();
bool empty();
};
class ParseTree {
private:
Node* root;
public:
ParseTree(string expression);
~ParseTree();
void recDelete(Node* ptr);
Node* doParse(string expression);
bool isOperand(char letter);
bool isOperator(char letter);
string inOrder();
string recInOrder(Node* ptr);
};