最近我编写了一个算法,在不使用任何堆栈的情况下将中缀表达式转换为二叉树.但是,当我在网上搜索时,我发现那里描述的算法都基于堆栈(或递归).

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

题

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

简短的介绍

它基于：

>中缀表达式中的操作数属于其前面的运算符的右子节点,或者属于它后面的运算符的左子节点.
>如果运算符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;