最近我写了一个算法来转换中缀EX pression一个二叉树，而无需使用任何堆栈。然而，当我搜索网，我发现算法描述存在都是基于栈（或递归）。

于是，我开始担心我的算法的正确性，虽然我不能证明 这是不正确呢。

问题的

你知不知道是否在技术上可以将其转换没有任何堆栈或不？是我的算法错了吗？

简短说明的

这是基于：

在中缀EX pression操作数所属的运营商在它的前面或者右孩子，或者运营商的左子后面。

如果运营商 OP2 具有较高的precedence比preceding运营商 OP1 中，previous操作数 X 变成 OP2 的左孩子，和 OP2 成为右子 OP1 。

如果运营商 OP2 具有较低的precedence比preceding运营商 OP1 中，previous操作数 X 变成 OP1 的右孩子。去了树，从 OP1 ，与 OP2 直到 OP2 ＆LT; =祖先 OP 。然后 OP2 变成 OP 。

程序的

 的#include＆LT;的iostream＆GT;
＃包括＆LT;字符串＆GT;
＃包括＆LT; sstream＆GT;
＃包括＆LT;＆了cassert GT;

使用名字空间std;

typedef结构节点{
   //商店经营者或操作
   字符串数据;
   //仅适用于运营商
   INT precedence;
   结构节点*父母;
   结构节点*离开;
   结构节点*权利;
} CNode，* PNode;

PNode CreateNode（常量字符串和放大器，X）
{
   PNode P =新CNode;
   P-＆GT;母公司= P-＆GT;左= P-＆GT;右= NULL;
   P-＆GT;数据= X;
   返回磷;
}

布尔IsOperator（常量字符串和放大器，X）
{
   //由于括号），唯一的影响（是precedence，
   //他们不认为是运营商在这里
   返程（（x.length（）== 1）及和放大器;
           （X [0] ==*||
            ×〔0] =='/'||
            ×〔0] ==+||
            ×〔0] ==' - '））;
}

布尔IsLeftParenthesis（常量字符串和放大器，X）
{
   返回X ==（;
}

布尔IsRightParenthesis（常量字符串和放大器，X）
{
   返回X ==）;
}

布尔IsOperand（常量字符串和放大器，X）
{
   诠释Ÿ;
   stringstream的SS（X）;
   如果（SS＆GT;＆GT; Y）返回true;
   否则返回false;
}

INT获取precedence（常量字符串和放大器，X）
{
   断言（IsOperator（X））;
   如果（X [0] =='*'|| X [0] =='/'）返回2;
   否则返回1;
}

PNode CreateInfixTree（常量字符串和放大器; EXP）
{
   //创建以最小的precedence一个虚拟根
   //它的内容是微不足道
   PNode根= CreateNode（0）;
   根 - ＆GT; precedence = INT_MIN;

   //当前运营商的previous操作
   PNode preOperand = NULL;
   //当前运营商的previous运营商
   PNode preOperator =根;
   // preceding括号，影响如果有的话
   INT校正= 0;

   字符串标记;
   stringstream的SS（EXP）;

   而（SS＆GT;＆GT;令牌）
   {
      如果（IsOperand（标记））
      {
         preOperand = CreateNode（标记）;
      }
      否则，如果（IsOperator（标记））
      {
         PNode P = CreateNode（标记）;
         P-＆GT; precedence =获取precedence（标记）+修正;
         如果（对GT; precedence＆GT; preOperator-＆GT; precedence）
         {
            P-＆GT;左= preOperand;
            preOperator-＆GT;右= P;
            P-＆GT;母公司= preOperator;
         }
         其他
         {
            preOperator-＆GT;右= preOperand;
            PNode Q = preOperator-＆GT;父母;
            而（对GT; precedence＆LT; = Q-＆GT; precedence）Q = Q-＆GT;父母;

            P-＆GT;左= Q-＆GT;权利;
            Q-＆GT;右= P;
            P-＆GT;母公司= Q;
         }
         preOperand = NULL;
         preOperator = P;

      } //否则如果（IsOperator（令牌）
      否则，如果（IsLeftParenthesis（标记））
      {
         校正+ = 2;
      }
      否则，如果（IsRightParenthesis（标记））
      {
         校正 -  = 2;
      }
      其他
      {
         COUT＆LT;＆LT; 非法令牌发现：＆LT;＆LT;令牌LT;＆LT; ENDL;
         打破;
      }
   }//而

   如果（preOperand == NULL）
       COUT＆LT;＆LT; 非法EX pression：无法与运营商结束：
            ＆LT;＆LT; preOperator-＆GT;数据＆LT;＆LT; ENDL;
   否则preOperator-＆GT;右= preOperand;

   //删除虚拟根
   PNode realRoot =根 - ＆GT;权利;
   删除根目录;
   如果（realRoot）realRoot-＆GT母体= NULL;
   返回realRoot;
}

无效PostOrderPrintTree（PNode节点）
{
   如果（节点）
   {
      PostOrderPrintTree（与于节点GT;左）;
      PostOrderPrintTree（与于节点GT;右一）;
      COUT＆LT;＆LT; - 于节点GT;数据＆LT;＆LT; ;
   }
}

诠释的main（）
{
   //有效的运算符：+  -  * /（）
   //有效的操作数：整数
   //空格分隔为：（1 + 2）* 3
   串EXP;
   函数getline（霉素，EXP）;
   PNode根= CreateInfixTree（EXP）;
   PostOrderPrintTree（根）;
   COUT＆LT;＆LT; ENDL;
}
 

解决方案

下面是你的栈：

 同时（对GT; precedence＆LT; = Q-＆GT; precedence）Q = Q-＆GT;父母;
 

Recently I wrote an algorithm to convert an infix expression to a binary tree without using any stack. However, as I search on web, I find the algorithms described there are all based on stack(or recursion).

So I begin to worry about the correctness about my algorithm, though I cannot prove it's incorrect yet.

Question

Do you know whether it's technically possible to convert it without any stack or not? Is my algorithm wrong?

Short description

It's based on:

An operand in an infix expression belongs to either the right child of the operator in front of it, or the left child of the operator behind it.

If an operator OP2 has higher precedence than its preceding operator OP1, the previous operand x becomes the left child of OP2, and OP2 becomes the right child of OP1.

If an operator OP2 has lower precedence than its preceding operator OP1, the previous operand x becomes the right child of OP1. Go up the tree from OP1, compare the precedence of each ancestor of OP1 with that of OP2 until OP2 <= ancestor OP. Then OP2 becomes the right child of OP.

The program

#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;
}

Here is your stack:

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