0

バイナリーツリーの再帰関数についての質問です。以下のテストプログラムを作ったりました。コンパイルはうまくいきますが、やりたいことができていません。これをコンパイルすると () が想定よりも多く表示されています。どのようにしたら ((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);

};
6
  • 「コンパイルできませんでした」というのは、質問のプログラムをコンパイルするとエラーが出るということですか? だったら、そのエラーメッセージよく読むことをお勧めします。
    – Fumu 7
    2021年10月29日 11:35
  • 途中で止まってしまい、エラーメッセージも表示されませんでした。 2021年10月29日 11:40
  • 2
    タイトルには質問の概要を端的に書いてください。日記ではありません。
    – htb
    2021年10月29日 12:33
  • コンパイラはvisual studioです。output.erase()がうまくいっていないようでしたので、消しました。それにあたり、質問も概要も少し変更しました。 2021年10月29日 13:30
  • その「()の想定」の基となった資料(何かの書籍・Web上の記事・ライブラリ/パッケージの仕様など)の情報は有りますか? そして「()が想定よりも多く表示されている」ことに何か問題があるのでしょうか?
    – kunif
    2021年10月29日 14:10

1 件の回答 1

1

ABといった単体の要素についても必ず前後に(,)を付けているからだと思われます。

ParseTree.cppstring ParseTree::recInOrder(Node* ptr)の以下の部分を:

    output = output + "(" +  recInOrder(ptr->getLeft());
    output = output + ptr->getValue();
    output = output + recInOrder(ptr->getRight()) + ")";

こちらのように左側、右側の要素が有る時だけ(,)を出力すればよいのでは?

    if (ptr->getLeft() != nullptr) {
        output = output + "(" + recInOrder(ptr->getLeft());
    }
    output = output + ptr->getValue();
    if (ptr->getRight() != nullptr) {
        output = output + recInOrder(ptr->getRight()) + ")";
    }

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。