дерево выражений не изменяется в функции simplifyAddition при передаче указателя на корень, как передать его по-другому?
#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. Однако после компиляции программы дерево остается неизменных. И проблема в том, что я не вижу, где именно ошибка и почему изменения не происходят.
Источник: Stack Overflow на русском