Uttrycksträd

Ett uttrycksträd är en datastruktur som används för att representera matematiska eller logiska uttryck som en trädliknande uppbyggnad. Varje intern nod i trädet motsvarar en operator (t.ex. +, −, *, /, likhet) och varje löv motsvarar en operand (t.ex. en konstant eller en variabel). Roten i trädet är oftast en operator, men kan också vara en enskild operand beroende på uttryckets form.

Uttrycksträd används vanligen inom datorprogrammering och beräkningar, där de fungerar som en mellan representation mellan källkod och maskinkod eller mellan olika optimeringssteg. Genom att traversera trädet kan man evaluera uttrycket, omvandla det till annan syntax eller optimera det inför kodgenerering. Vanliga operationer inkluderar rekursiv utvärdering av trädet, förenkling av uttryck, samt konstantutveckling där delar av trädet som består av konstanter beräknas i förväg.

Exempelvis motsvarar uttrycket (a + b) * c ett träd där roten är operatorn *, vänstra barnet är operatorn + med operands användande a och b, och högra barnet är operand c. Sådana representationer förenklar manipulation av uttryck i kompilatorer, grafiska räknare och symboliska algebra-system.

Relaterat till parse-träd och abstrakta syntax-träd (AST) utgör uttrycksträd ofta en delmängd eller understruktur i ett AST, där de fokuserar på det faktiska uttrycket snarare än hela programsatsen.