Build a binary tree from an infix expression without using a stack
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 operatorOP1
, the previous operandx
becomes the left child ofOP2
, andOP2
becomes the right child ofOP1
.If an operator
OP2
has lower precedence than its preceding operatorOP1
, the previous operandx
becomes the right child ofOP1
. Go up the tree fromOP1
, compare the precedence of each ancestor ofOP1
with that ofOP2
untilOP2
<= ancestorOP
. ThenOP2
becomes the right child ofOP
.
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 strin开发者_开发技巧g& 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;
精彩评论