Expression Tree from Infix Expression in C++ Structural Programming

Question

struct node
{
 char data;
 node *left, *right;
};

constructTree(string expression)
{
 for(i = 0; i < expression.length(); i++)
 {
  if(!(isOperator(expression[i]))
  {
   temp = createNode(expression[i]);
   push(temp);
  }
  else
  {
   temp = createNode(expression[i]);
   node *temp1, *temp2;
   temp1 = pop();
   temp2 = pop();
   temp->left = temp1;
   temp->right = temp2;
  }
 }
}

int main()
{
 string expression = "(a+b)-c*(d/e)";
 constructTree(expression);
}

I want to construct expression tree from infix expression which I will take as a string from the user. I tried so much now I am feeling tired of it. Some body please help me in making this expression tree from infix expression!

Please give a [MCVE]. Whatever, if you had search on Internet you would have find https://softwareengineering.stackexchange.com/questions/290529/algorithm-to-go-from-infix-notation-to-a-tree — Jean-Baptiste Yunès, Dec 18 '19 at 20:21
You will have a better Stack Overflow experience if you attempt to solve the problem and ask questions, if necessary, about the attempt. — user4581301, Dec 18 '19 at 20:21
Writing an expression parser is a non-trivial amount of work, and there are a lot of ways to go about doing it. But you're not the first person to ask. do any of these answers help? https://stackoverflow.com/questions/11703082/parsing-math-expression-in-c — parktomatomi, Dec 18 '19 at 20:22
Out of curiosity, what happens when your program encounters a two-character operator like `==`? — Thomas Matthews, Dec 18 '19 at 21:54
Last I remember, you build a tree from the expression. The traversing algorithm determined whether you got Postfix, Infix, or Prefix notation. — Thomas Matthews, Dec 18 '19 at 21:59
Please edit your post with the results of your debugging session. For example, which statement causes the issue? What are the values of the variables in that statement? What are expected values? — Thomas Matthews, Dec 18 '19 at 22:01
I have a python implementation in this answer, along with the secret of how to do this yourself without a whole lot of code: https://stackoverflow.com/questions/42610626/is-it-necessary-to-convert-infix-notation-to-postfix-when-creating-an-expression/42612892#42612892 — Matt Timmermans, Dec 18 '19 at 22:14

score 0 · Answer 1 · answered Dec 18 '19 at 21:28

You are trying to write a parser.

There are so many ways to do this, with some ways being especially optimized for infix expressions, and others being more general.

I personally suggest reading about Recursive Descent parsers, as they are a good starting point to learn about parsers since they are relatively simple and intuitive.

A simple recursive descent parser that handles expression with addition, subtraction, multiplication, division and parentheses would look something like this (This is pseudocode!):

node* readExpr() {
    return readAddOrSub();
}

node* readAddOrSub() {
    leftTree = readMulOrDiv();
    token = peekNextToken();  // look at the next token without consuming it 
    if (token == '+' || token == '-') {
         readNextToken();  // skip operator
         rightTree = readAddOrSub();
         return an addition or subtraction node with leftTree and rightTree as its left and right sub-trees respectively;
    } else {
         return leftTree;
    }
}

node* readMulOrDiv() {
    leftTree = readAtom();
    token = peekNextToken();
    if (token == '*' || token == '/') {
         readNextToken();  // skip operator
         rightTree = readMulOrDiv();
         return a multiplication node with leftTree and rightTree as its left and right sub-trees respectively;
    } else {
         return leftTree;
    }
}

node* readAtom() {
    token = readNextToken()
    if (token == '(') {
         result = readExpr();
         read another token and make sure it's ')';
         return result;
    } else if (token is a number)
         return node holding a number;
    else if (token is a variable)
         return node holding a variable;
    else
         error();
}

This assumes you have something that breaks up your string apart into tokens (e.g. "5*(a+12)" should be broken into 7 tokens: the number 5, '*', '(', the variable 'a', '+', the number 12, ')').

Operator precedence is captured by the way that functions that parse an opeator of a certain precedence level call the functions that handle the next level of precedence in a hierarchical fashion. More specifically, a function that tries to parse an addition/subtraction node (readAddOrSub) calls the function that parses the next level of precedence (readMulOrDiv) to get its left and right sub-trees.

Note that readAddOrSub (and readMulOrDiv) calls itself to read the right-subtee so that multiple additions can be chained together ("1+2+3"), but beware that this makes the parser inherently right-associative ("1+2+3" will be parsed as "1+(2+3)").

Of course, it's not very hard to make it left-associative, but I'll leave that to you as an exercise!

Some resources that might help:

Expression Tree from Infix Expression in C++ Structural Programming

1 Answers1