最近我写了一个算法在不使用任何堆栈的情况下将中缀表达式转换为二叉树
。然而,当我在网上搜索时,我发现那里描述的算法都是基于堆栈(或递归)的。
所以我开始担心我算法的正确性,虽然我无法证明 它还不正确。
问题
你知道在技术上是否可以在没有任何堆栈的情况下转换它吗?我的算法错了吗?
简短描述
它基于:
中缀表达式中的操作数要么属于它前面的运算符的右 child ,要么属于它后面的运算符的左 child 。
如果运算符
OP2
的优先级高于其前一个运算符OP1
,则前一个操作数x
成为OP2
,OP2
成为OP1
的右 child 。如果运算符
OP2
的优先级低于其前一个运算符OP1
,则前一个操作数x
成为OP1
。从OP1
上树,比较OP1
和OP2
每个祖先的优先级,直到OP2
< = 祖先OP
。然后OP2
成为OP
的右 child 。
程序
#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++ - 在不使用堆栈的情况下从中缀表达式构建二叉树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6973528/