File ExpressionTree.h

↰ Parent directory (ADS/tree)

The tree of an arithmetic expression (the parse tree), beyond the book: a binary tree [see File BinaryTree.h] whose leaves are the operands, numbers or names of variables, and whose internal nodes are the binary operators.

Definition (ADS/tree/ExpressionTree.h)

Detailed Description

      • / ^ (the power), the left subtree being the left operand.

  • expressionTree() builds it from the postfix form of the expression [see File Expressions.h] with a stack of trees: an operand is pushed as a leaf, an operator pops its right and then its left subtree and pushes the new tree, in O( n );

  • evaluate() computes its value by a postvisit, the values of the variables given by a dictionary;

  • prefixForm() writes it in prefix form, each subtree in parentheses, e.g., (*(/(3)(+(*(^(x)(2))(y))(*(3)(x))))(-(z)(1))) for ( 3 / ( x^2 y + 3 x ) ) ( z - 1 ), and infixForm() in infix form, fully parenthesized, by an invisit.

The contracts [see File Contract.h]: the postfix expression is well formed, i.e., each operator finds two subtrees and one tree is left; evaluate() needs a value for each variable, and no division by 0. The functions are defined in ExpressionTree.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, sections 5.5 and 5.6, https://algoritmicamente.it/materiali/libro/capitoli/cap05.pdf

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions