

バイナリーツリーを使って計算式を表示するプログラムを作りました。しかしながら、このプログラムで表示される計算式は正しくありません。実際にやりたいことは、必要な部分は
`()` を使い、不必要な `()` は除くか、または表示させないようにしたいです。例えば、`(A+B)*C+D*(F/G)`
をparseInOrderメソッドに渡し、inOrderを使って表示させると`(A+B)*C+D*F/G` のように表示できるようにしたいです。

そこで、動作確認のための計算式を二個用意しました。この二個の計算式が想定通りに変形される様にプログラムを修正したいです。一つはうまくいっていますが、もう一つは計算式としては間違えています。問題はrecInOrderメソッド内にあることはわかっていますが、解決策が分かりません。recInOrderは再帰関数なので、複雑でいろいろ試してみましたが、今の方法が一番近いと思ったのでこの方法を載せました。解決策が分かる方、よろしくお願いします。

**main.cpp**

[code]

    #include <iostream>
    #include "ParseTree.h"
    
    int main(int argc, const char * argv[]) {
    
        std::cout << "Testing Thinking Problem" << std::endl << std::endl;
    
        std::string expression5 = "(A+B)*C+D*(F/G)";
        std::string expression6 = "A*B+(C-D)";
        ParseTree ptree4("");
    
        ptree4.parseInOrder(expression5);
        std::cout << "Input is (A+B)*C+D*(F/G)" << std::endl;
        std::cout << "In Order should be (A+B)*C+D*F/G and is " << ptree4.inOrder() << std::endl << std::endl;
    
    
        ptree4.parseInOrder(expression6);
        std::cout << "Input is A*B+(C-D)" << std::endl;
        std::cout << "In Order should be A*B+C-D and is " << ptree4.inOrder() << std::endl << std::endl;
    
    
        std::cout << "Done with Testing Thinking Problem" << 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;
        }
    
    
        if(ptr->getLeft() != nullptr){
    
            if(ptr->getValue() == '*' || ptr->getValue() == '/')
            {
                if(ptr->getLeft()->getValue() == '+' || ptr->getLeft()->getValue() == '-')
                {
                    output += "(";
                }
            }
        }
    
        output = output + recInOrder(ptr->getLeft());
    
        if(ptr->getLeft() != nullptr){
    
            if(ptr->getValue() == '*' || ptr->getValue() == '/')
            {
                if(ptr->getLeft()->getValue() == '+' || ptr->getLeft()->getValue() == '-')
                {
                    output += ")";
                }
            }
        }
    
    
        output = output + ptr->getValue();
    
        output = output + recInOrder(ptr->getRight());
    
    
        return output;
    }
    
    
    
    
    void ParseTree::parseInOrder(string infix)
    {
        recDelete(root);
        string postfix = inOrder2PostOrder(infix);
        root = doParse(postfix);
    }
    
    
    string ParseTree::inOrder2PostOrder(string expression)
    {
        Stack theStack;
        string output = "";
    
        for(int i = 0; i < expression.length(); i++)
        {
            //get a letter from input
            char letter = expression[i];
    
            //if letter is operand, save it in string
            if(isOperand(letter) == true)
            {
                output += letter;
            }
                //if letter is (, push
            else if(letter == LPAREN)
            {
                theStack.push(new Node(letter));
            }
                //if letter is ),
            else if(letter == RPAREN)
            {
                bool isPopping = true;
                while(!theStack.empty() && isPopping)
                {
                    Node* markNode = theStack.top();
                    char value = markNode->getValue();
                    theStack.pop();
                    if(value == LPAREN)
                    {
                        isPopping = false;
                    }
                    else
                    {
                        output += value;
                    }
                }
            }
                //if letter is operator
            else if(isOperator(letter) == true)
            {
                bool isPopping = true;
                while(!theStack.empty() && isPopping)
                {
                    //get the value in the stack
                    Node* markNode = theStack.top();
                    char value = markNode->getValue();
                    theStack.pop();
    
                    //if value is (
                    if(value == LPAREN)
                    {
                        theStack.push(new Node(value));
                        isPopping = false;
                    }
                    else
                    {
                        //if the precedence of value isn't higher than letter
                        if(!isHigher(value, letter))
                        {
                            //push the value and stop the loop
                            theStack.push(new Node(value));
                            isPopping = false;
                        }
                            //if the precedence of value is higher than letter
                        else
                        {
                            //value should be moved to string
                            output += value;
                        }
                    }
                }
                theStack.push(new Node(letter));
            }
        }
        while(!theStack.empty())
        {
            Node* markNode = theStack.top();
            char value = markNode->getValue();
            output += value;
            theStack.pop();
        }
        return output;
    }
    
    bool ParseTree::isHigher(char value, char compare)
    {
        int valPrec = 0;
        int comPrec = 0;
        if(value == '+' || value == '-')
        {
            valPrec = 1;
        }
        else if(value == '*' || value == '/')
        {
            valPrec = 2;
        }
    
        if(compare == '+' || compare == '-')
        {
            comPrec = 1;
        }
        else if(value == '*' || value == '/')
        {
            comPrec = 2;
        }
    
        if(valPrec >= comPrec)
        {
            return true;
        }
        return false;
    }
    
[/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);
        
        void parseInOrder(string infix);
        string inOrder2PostOrder(string input);
        bool isHigher(char value1, char value2);
    };
    
[/code]


CC BY-SA 4.0
2021-10-30T01:33:53.967
83337
2021-10-30T04:08:13.420
2021-10-30T04:08:13.420
3060
45177
question
c++
バイナリーツリーの再帰関数がどのように動くか理解できていないため、プログラムが理想の動きをしない


テストが通らない原因は、recInOrderメソッドではなく、isHigherメソッドです。  
単純なミスなので、落ち着いて見ればわかると思います。


CC BY-SA 4.0
2021-10-30T02:34:28.663
83338
2021-10-30T02:34:28.663
43506
83337
answer