Решено: Построение дерева из постфиксного выражения C ++ - PullRequest
Новая
       74

Решено: Построение дерева из постфиксного выражения C ++

1 голос
/ 10 октября 2019

В настоящее время я работаю над вычислением значения переменного постфиксного выражения, например. ab + bc - *. Для определенного состояния, a = 1 b = 2 и c = 0, я могу решить это с помощью стека. Из-за множества возможных заданных состояний (около 10 ^ 6) и расчета каждого значения весь процесс становится действительно медленным.

Поэтому я пытаюсь построить двоичное дерево, где листья хранят мои переменные или логические выражения. После получения необходимых значений для листьев я могу просто вычислить значение, используя дерево, без необходимости использовать стеки или выполнять итерации каждый раз над выражением.

Моя проблема заключается в построении соответствующего дерева. Я использую структуру для своих узлов с указателями на дочерние элементы и сохраняю ее в векторе 

struct Node {
  string name;
  int value;
  int level;
  Node* lChild;
  Node* rChild;
};


vector<Node> tree;

void build_tree(string input) {
  const string ops = "&&||+*-/";
  std::stringstream ss(input);
  std::stack<Node> s;
  std::string token;
  while(std::getline(ss, token, ' ')) {
    if(ops.find(token) != string::npos) {
      Node rChild = s.top(); s.pop();
      Node lChild = s.top(); s.pop();
      Node n = {token, 0, 1, &lChild, &rChild};
      tree.insert(tree.end(), n);
      s.push(n);
    } else {
      Node n = {token, 0, 0, NULL, NULL};
      tree.insert(tree.begin(), n);
      s.push(n);
    }
  }
}

. После построения дерева каждый lChild и rChild указывают на один и тот же последний использованный адрес. Для тестирования я использовал выражение «4 5 + 3 1 - * 9 /». Каждый узел, кроме листьев, в моем дереве имеет lChild.name = '*' и rChild.name = '9'

Есть ли критическая точка, которую я упускаю при использовании указателей?

РЕДАКТИРОВАТЬ: Я нашел свою ошибку. Я забыл выделить память на кучу 

vector<Node*> tree;

void build_tree(string input) {
  ...
  std::stack<Node*> s;
  ...
      Node* rChild = s.top(); s.pop();
      Node* lChild = s.top(); s.pop();
      Node* n = new Node(token, 0, 1, lChild, rChild);
      ...
      Node* n = new Node(token, 0, 0, NULL, NULL);
      ...
  }

Спасибо за помощь.

...