

バイナリーツリーの再帰関数についての質問です。以下のテストプログラムを作ったりました。コンパイルはうまくいきますが、やりたいことができていません。これをコンパイルすると
`()` が想定よりも多く表示されています。どのようにしたら `((A+B)*(C-D))` と `(((A-B)+C)*(D/E))`
のように表示できますか。

ptrがnullptrに到達したときにoutputの最後の文字を消すことができれば解決できるように思えるのですが、最後の文字の消し方もわかりません。この問題を解ける方よろしくお願いします。

**main.cpp**

[code]

    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;
    }
    
[/code]

**ParseTree.cpp**

[code]

    #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;
    }
    
[/code]

**ParseTree.h**

[code]

    #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);
    
    };
    
[/code]


CC BY-SA 4.0
2021-10-29T10:13:20.477
83328
2021-10-30T04:10:38.800
2021-10-30T04:10:38.800
3060
45177
question
c++
バイナリーツリーの再帰関数についての質問です。以下をコンパイルすると () が想定よりも多く表示されています。もう少しコンパクトに表示したい


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

`ParseTree.cpp`の`string ParseTree::recInOrder(Node* ptr)`の以下の部分を：

[code]

        output = output + "(" +  recInOrder(ptr->getLeft());
        output = output + ptr->getValue();
        output = output + recInOrder(ptr->getRight()) + ")";
    
[/code]

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

[code]

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


CC BY-SA 4.0
2021-10-29T16:23:48.973
83335
2021-10-29T16:23:48.973
26370
83328
answer