# [lintcode] Expression Tree Build

Expression Tree Build

The structure of Expression Tree is a binary tree to evaluate certain expressions. All leaves of the Expression Tree have an number string value. All non-leaves of the Expression Tree have an operator string value.

Now, given an expression array, build the expression tree of this expression, return the root of this expression tree.

Have you met this question in a real interview?

Example

For the expression `(2*6-(23+7)/(1+2))` (which can be represented by [“2” “*” “6” “-” “(” “23” “+” “7” “)” “/” “(” “1” “+” “2” “)”]). The expression tree will be like

``````                 [ - ]
/          \
[ * ]              [ / ]
/     \           /         \
[ 2 ]  [ 6 ]      [ + ]        [ + ]
/    \       /      \
[ 23 ][ 7 ] [ 1 ]   [ 2 ] .
``````

After building the tree, you just need to return root node `[-]`.

Clarification

See wiki: Expression Tree

Tags

Related Problems

Use two stacks, operand and operator.

```/**
* Definition of ExpressionTreeNode:
* class ExpressionTreeNode {
* public:
*     string symbol;
*     ExpressionTreeNode *left, *right;
*     ExpressionTreeNode(string symbol) {
*         this->symbol = symbol;
*         this->left = this->right = NULL;
*     }
* }
*/

class Solution {
public:
/**
* @param expression: A string array
* @return: The root of expression tree
*/
ExpressionTreeNode* build(vector<string> &expression) {
stack<ExpressionTreeNode *> operators, operands;
for(int i = 0; i < expression.size(); ++i){
auto exp = expression[i];
ExpressionTreeNode * p = new ExpressionTreeNode(exp);
if(exp[0] <= '9' || exp[0] >= '0'){
//digit
operands.push(p);
}
else{
//operator
if(operators.empty()){
operators.push(p);
}else if(exp[0] == '('){
operators.push(p);
}else if(exp[0] == ')'){
while(operators.top() != '('){
eval(operators, operands);
}
operators.pop();//pop ')'
}else if(getPriority(p) > getPriority(operators.top())){
operators.push(p);
}else{
//evaluate
eval(operators, operands);
delete p;
i--;
}
}
}
while(!operators.empty()){
eval(operators, operands);
}
return operands.top();
}
void eval(stack<ExpressionTreeNode *>& operators, stack<ExpressionTreeNode *>& operands){
ExpressionTreeNode * oper = operators.top();
operators.pop();
ExpressionTreeNode * operand1 = operands.top();
operands.pop();
ExpressionTreeNode * operand2 = operands.top();
operands.pop();
oper->right = operand1;
oper->left = operand2;
operands.push(oper);
}
int getPriority(ExpressionTreeNode* a){
char c = a->symbol[0];
if(c == '+' || c == '-'){
return 1;
}
else if(c == '*' || c == '/'){
return 2;
}
}
};
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.