c – 在不使用堆栈的情况下从中缀表达式构建二叉树

概述最近我编写了一个算法,在不使用任何堆栈的情况下将中缀表达式转换为二叉树.但是,当我在网上搜索时,我发现那里描述的算法都基于堆栈(或递归). 所以我开始担心我的算法的正确性,尽管我无法证明 这是不正确的. 题 你知道技术上是否可以在没有任何堆栈的情况下进行转换？我的算法错了吗？ 简短的介绍 它基于： >中缀表达式中的 *** 作数属于其前面的运算符的右子节点,或者属于它后面的运算符的左子节点. >如果运算符 最近我编写了一个算法,在不使用任何堆栈的情况下将中缀表达式转换为二叉树.但是,当我在网上搜索时,我发现那里描述的算法都基于堆栈(或递归).

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

题

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

简短的介绍

它基于：

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

总结

以上是内存溢出为你收集整理的c – 在不使用堆栈的情况下从中缀表达式构建二叉树全部内容，希望文章能够帮你解决c – 在不使用堆栈的情况下从中缀表达式构建二叉树所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。