c++ - 从infix表达式构建二叉树而无需使用堆栈

最近，我为convert an infix expression to a binary tree without using any stack编写了一种算法。但是，当我在网络上搜索时，发现其中描述的算法全部基于堆栈(或递归)。

所以我开始担心算法的正确性，尽管我无法证明
这是不正确的。

问题

您知道在没有任何堆栈的情况下进行转换是否在技术上可行吗？我的算法错了吗？

简短说明

它基于:

infix表达式中的操作数属于它前面的运算符的右子元素，或者属于它后面的运算符的左子元素。

如果运算符OP2的优先级高于其前面的运算符OP1，则前一个操作数x成为OP2的左子代，而OP2成为OP1的右子代。

如果运算符OP2的优先级低于其前面的运算符OP1，则前一个操作数x成为OP1的右子级。从OP1上树，将OP1的每个祖先的优先级与OP2的优先级进行比较，直到OP2 OP为止。然后OP2成为OP的正确子代。

程序

#include <iostream>
#include <string>
#include <sstream>
#include <cassert>

using namespace std;

typedef struct Node{
   // store operator or operand
   string data;
   // only valid for operator
   int precedence;
   struct Node* parent;
   struct Node* left;
   struct Node* right;
}CNode, *PNode;

PNode CreateNode(const string& x)
{
   PNode p = new CNode;
   p->parent = p->left = p->right = NULL;
   p->data = x;
   return p;
}

bool IsOperator(const string& x)
{
   // Since the only impact of parentheses () is on precedence,
   // they are not considered as operators here
   return ((x.length() == 1) &&
           (x[0] == '*' ||
            x[0] == '/' ||
            x[0] == '+' ||
            x[0] == '-'));
}

bool IsLeftParenthesis(const string& x)
{
   return x == "(";
}

bool IsRightParenthesis(const string& x)
{
   return x == ")";
}

bool IsOperand(const string& x)
{
   int y;
   stringstream ss(x);
   if (ss >> y) return true;
   else return false;
}

int GetPrecedence(const string& x)
{
   assert(IsOperator(x));
   if (x[0] == '*' || x[0] == '/') return 2;
   else return 1;
}

PNode CreateInfixTree(const string& exp)
{
   // create a dummy root with minimal precedence
   // its content is trivial
   PNode root = CreateNode("0");
   root->precedence = INT_MIN;

   // the previous operand of current operator
   PNode preOperand = NULL;
   // the previous operator of current operator
   PNode preOperator = root;
   // the impact of preceding parenthesis, if any
   int correction = 0;

   string token;
   stringstream ss(exp);

   while (ss >> token)
   {
      if (IsOperand(token))
      {
         preOperand = CreateNode(token);
      }
      else if (IsOperator(token))
      {
         PNode p = CreateNode(token);
         p->precedence = GetPrecedence(token) + correction;
         if (p->precedence > preOperator->precedence)
         {
            p->left = preOperand;
            preOperator->right = p;
            p->parent = preOperator;
         }
         else
         {
            preOperator->right = preOperand;
            PNode q = preOperator->parent;
            while (p->precedence <= q->precedence) q = q->parent;

            p->left = q->right;
            q->right = p;
            p->parent = q;
         }
         preOperand = NULL;
         preOperator = p;

      }//else if (IsOperator(token)
      else if (IsLeftParenthesis(token))
      {
         correction += 2;
      }
      else if (IsRightParenthesis(token))
      {
         correction -= 2;
      }
      else
      {
         cout << "illegal token found: " << token << endl;
         break;
      }
   }//while

   if (preOperand == NULL)
       cout << "illegal expression: cannot end with operator: "
            << preOperator->data << endl;
   else preOperator->right = preOperand;

   // delete dummy root
   PNode realRoot = root->right;
   delete root;
   if (realRoot) realRoot->parent = NULL;
   return realRoot;
}

void PostOrderPrintTree(PNode node)
{
   if (node)
   {
      PostOrderPrintTree(node->left);
      PostOrderPrintTree(node->right);
      cout << node->data << " ";
   }
}

int main()
{
   // valid operators: + - * / ( )
   // valid operands: integers
   // whitespace separated as: ( 1 + 2 ) * 3
   string exp;
   getline(cin, exp);
   PNode root = CreateInfixTree(exp);
   PostOrderPrintTree(root);
   cout << endl;
}

最佳答案

这是您的堆栈:

while (p->precedence <= q->precedence) q = q->parent;