дерево выражений не изменяется в функции simplifyAddition при передаче указателя на корень, как передать его по-другому?

Рейтинг: -1Ответов: 1Опубликовано: 04.06.2023
#include <iostream>
#include <stack>
#include <queue>
#include <string>
#include <map>

using namespace std;

struct Node {
    string value;
    Node* left;
    Node* right;
    Node(string v) : value(v), left(nullptr), right(nullptr) {}
};

Node* postfixToExpressionTree(queue<string> postfix) {
    stack<Node*> nodeStack;
    while (!postfix.empty()) {
        string token = postfix.front();
        postfix.pop();
        if (isdigit(token[0])) {
            Node* node = new Node(token);
            nodeStack.push(node);
        }
        else {
            Node* node = new Node(token);
            if (!nodeStack.empty()) { // проверка на пустой стек
                Node* right = nodeStack.top();
                nodeStack.pop();
                node->right = right;
            }
            if (!nodeStack.empty()) { // проверка на пустой стек
                Node* left = nodeStack.top();
                nodeStack.pop();
                node->left = left;
            }
            nodeStack.push(node);
        }
    }
    return nodeStack.top();
}

void printTree(Node* root) {
    if (root) {
        cout << root->value << " ";
        printTree(root->left);
        printTree(root->right);
    }
}


int priority(char op) {
    if (op == '+' || op == '-') { // исправлено здесь
        return 1;
    }
    if (op == '*' || op == '/') { // исправлено здесь
        return 2;
    }
    return 0;
}

queue<string> infixToPostfix(string expression) {
    stack<char> opStack;
    queue<string> output;
    string token;

    for (int i = 0; i < expression.length(); i++) {
        char c = expression[i];
        if (isdigit(c)) {
            token += c;
        }
        else {
            if (!token.empty()) {
                output.push(token);
                token = "";
            }
            if (c == '(') {
                opStack.push(c);
            }
            else if (c == ')') {
                while (!opStack.empty() && opStack.top() != '(') {
                    output.push(string(1, opStack.top()));
                    opStack.pop();
                }
                if (!opStack.empty()) {
                    opStack.pop(); // удалить "(" из стека
                }

            }
            else {
                while (!opStack.empty() && priority(c) <= priority(opStack.top())) {
                    output.push(string(1, opStack.top()));
                    opStack.pop();
                }
                opStack.push(c);
            }
        }
    }
    if (!token.empty()) {
        output.push(token);
    }
    while (!opStack.empty()) {
        output.push(string(1, opStack.top()));
        opStack.pop();
    }
    return output;
}

void simplifyAddition(Node* root) {
    if (root->value == "+") {
        Node* left = root->left;
        Node* right = root->right;
        if (root->value == "+" && root->left && root->right && isdigit(root->left->value[0]) && isdigit(root->right->value[0])) {
            int sum = stoi(root->left->value) + stoi(root->right->value);
            root->value = to_string(sum);
            root->left = nullptr;
            root->right = nullptr;
            //delete left;
           // delete right;
        }
    }
    if (root->left) {
        simplifyAddition(root->left);
    }
    if (root->right) {
        simplifyAddition(root->right);
    }
}

int main() {
    // Пример использования
    string expression = "2 + a + 2";
    queue<string> postfix = infixToPostfix(expression);
    Node* root = postfixToExpressionTree(postfix);
    cout << "Expression tree: \n";
    printTree(root);
    simplifyAddition(root);
    cout << endl;
    printTree(root);
    return 0;
}

У меня есть такой код, который преобразовывает выражение в постфиксную форму, а затем посимвольно кладет его в дерево выражений. Так вот, моя основная задача - делать преобразования в дереве, если встречается знак "+". То есть если у нас есть выражение "2 + а + 2", то оно должно преобразоваться в "а + 4". За это отвечает функция simplifyAddition. Однако после компиляции программы дерево остается неизменных. И проблема в том, что я не вижу, где именно ошибка и почему изменения не происходят.

Вывод примерно такой

Ответы

▲ 0

Разобрался.
В дерево помещались знаки пробела, в этом и была проблема.