Сборка двоичного дерева выражений С++

Я сделал алгоритм, который строит двоичное дерево из простого выражения. Но мне нужны скобки для каждого действия. например, я могу преобразовать это выражение: (2+(3*5)). В математике все нормально, если нет скобок, но мой алгоритм может работать без них. Есть ли способ сделать алгоритм, который может создать двоичное дерево выражений, которое работает с этим выражением: 2+3*5? Вот мой алгоритм, который требует скобок для каждого действия:

void Tree::MakeTree(string expr, int &pos, Node *node)
{
 if(expr[pos] == '(')
 {
 pos++;
 node->Left = new Node;
 node->Left->Left = NULL;
 node->Left->Right = NULL;
 MakeTree(expr, pos, node->Left);
 MakeTree(expr, pos, node);
 return;
 }

 if(expr[pos] >= '0' && expr[pos] <= '9')
 {
 node->data = expr[pos];
 pos++;
 return;
 }

 if(expr[pos] == '+' || expr[pos] == '-' || expr[pos] == '*' || expr[pos] == '/')
 {
 node->data = expr[pos];
 pos++;
 node->Right = new Node;
 node->Right->Left = NULL;
 node->Right->Right = NULL;
 MakeTree(expr, pos, node->Right);
 }

 if(expr[pos] == ')') 
 {
 pos++;
 return;
 }
}

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

1 ответ

То, как вы пытаетесь решить свою проблему, слишком упрощено. Это не сработает. Зачем? Потому что, как вы реагируете на определенный символ, зависит не только от самого символа, но и в каком контексте вы получаете этот символ. Таким образом, вам придется реализовать конечный автомат, и в разных состояниях вы будете реагировать по-разному даже на один и тот же вход. Например, когда вы получаете символ "-", что это такое, часть выражения типа "5-3" или унарный минус из "-6"? Это зависит от того, в каком состоянии вы находитесь, когда вы получили этот символ. Таким образом, реализация полной логики обработки синтаксического анализа не так проста и хуже монотонна. Поэтому в реальных программах люди обычно не делают это вручную, но используют специальные инструменты, такие как lex/flex или boost, и т.д. Это не значит, что вы не можете реализовать это для обучения, но ответ на этот вопрос, вероятно, будет слишком большим для формата stackoverflow, и во многих книгах уже ответили. Поэтому найдите хорошую книгу для синтаксического разбора или попробуйте найти учебное пособие в Интернете, как реализовать простой калькулятор.

licensed under cc by-sa 3.0 with attribution.