Infix notation
Infix notation is a conventional method of expressing mathematical and logical operations in which the operator is placed between its operands, as in the expression a + b, making it the most intuitive and widely used format for human-readable arithmetic and algebraic statements.[1] This notation requires explicit rules for operator precedence and associativity—such as multiplication preceding addition—and parentheses to resolve ambiguities in evaluation order, ensuring unambiguous computation.[2] Originating from ancient mathematical practices, infix notation evolved significantly during the Renaissance, with key symbols like the plus sign emerging as a shorthand for "et" (Latin for "and") by the late 1400s, and algebraic forms solidifying in the early 1600s through contributions from mathematicians like François Viète and William Oughtred.[3] By the 1700s, figures such as Gottfried Wilhelm Leibniz and Leonhard Euler further standardized it, introducing notations for powers and integrals that remain in use today.[3] In computer science, infix notation dominates programming languages due to its readability, though it poses parsing challenges compared to alternatives like prefix (Polish) or postfix (reverse Polish) notations, which eliminate the need for precedence rules and are more efficient for stack-based evaluation.[4] Despite these complexities, it has cemented infix as the foundational notation for mathematics education and scientific communication since the 19th century.[2]
Fundamentals
Definition
Infix notation is a syntactic form in which binary operators are placed between their two operands, adhering to the general structure A op B, where A and B represent the operands and op denotes the operator.[5] This positioning of the operator directly between the elements it connects forms the core characteristic of the notation.[6]
Infix notation differs from alternative syntactic forms in the placement of operators relative to operands, with operators appearing either preceding or following them in other systems.[6]
A formal syntactic definition of infix notation for expressions, such as arithmetic ones, is typically provided through a context-free grammar in Backus-Naur Form (BNF). One standard grammar structure is as follows:
E → E + T | E - T | T
T → T * F | T / F | F
F → ( E ) | id
E → E + T | E - T | T
T → T * F | T / F | F
F → ( E ) | id
Here, E denotes an expression non-terminal handling additive operations, T a term non-terminal for multiplicative operations, F a factor non-terminal for atomic elements or parenthesized subexpressions, + and - represent addition and subtraction operators, * and / multiplication and division operators, ( and ) parentheses, and id a terminal for identifiers. This recursive grammar enforces operator precedence via non-terminal hierarchy and left-associativity through the production rules.[6]
Infix notation serves a primary role in facilitating human-readable mathematical expressions, mirroring conventional writing practices that enhance comprehension of operational relationships.[7] To address ambiguities arising from multiple operators, it relies on established rules for order of operations.[6]
Basic Examples
Infix notation is exemplified by simple arithmetic expressions where the operator is placed between two numeric operands. For instance, the expression $2 + 3 denotes the addition of the numbers 2 and 3, resulting in 5.[8] Similarly, $5 \times 4 represents the multiplication of 5 and 4, yielding 20.[9]
In algebraic expressions, variables replace or supplement numbers, maintaining the operator's position between operands. A basic example is a \times b, which signifies the product of variables a and b.[9] Another common form is x + y \times z, where the multiplication of y and z is understood to occur before the addition with x, illustrating operator precedence in infix structures.[9]
Parentheses in infix notation explicitly group operands and operators to override default precedence rules, dictating the evaluation order. For example, (2 + 3) \times 4 first computes the sum inside the parentheses (yielding 5) and then multiplies by 4, resulting in 20, whereas $2 + 3 \times 4 without parentheses evaluates to 14 due to multiplication's higher precedence.[9]
The hierarchical structure of an infix expression can be visualized using a parse tree, which represents the grammar's derivation and operator associations. For the expression a + b - c, assuming left-to-right associativity for operators of equal precedence, the parse tree is as follows:
-
/ \
+ c
/ \
a b
-
/ \
+ c
/ \
a b
This tree indicates subtraction as the root operation, with its left subtree being the addition of a and b, and the right subtree simply c; the expression evaluates as (a + b) - c.[10]
Historical Context
Origins in Mathematics
Infix notation, where operators are placed between operands, emerged gradually in mathematical writing as a means to express relations more symbolically than purely verbal descriptions. One of the earliest instances appears in the works of Diophantus of Alexandria in the 3rd century AD, who employed a syncopated notation in his Arithmetica that included abbreviations for the unknown quantity and its powers, along with a symbol for equality placed between the sides of an equation, though operations were often indicated verbally or by juxtaposition, marking a preliminary shift toward symbolic placement. For example, Diophantus represented expressions like the sum of terms or equations using abbreviated Greek symbols interspersed among numbers and variables, such as a symbol resembling a final sigma for the unknown.[11]
The development of infix notation advanced significantly during the Renaissance with the introduction of specific symbols for addition and subtraction. In 1489, German mathematician Johannes Widmann first printed the plus (+) and minus (−) signs in his treatise Behende und hüpsche Rechenung auf allen Kauffmannschafft (Mercantile Arithmetic), initially using them to denote surpluses and deficits in commercial contexts rather than general operations, though they were soon adapted for arithmetic between terms. These symbols were popularized in England by Robert Recorde in 1557 in The Whetstone of Witte, where he explicitly defined + as denoting "more" (from surplus) and − as "less" (from defect), facilitating infix expressions like 4 + 5 = 9 in practical calculations. This innovation built on earlier medieval abbreviations like p (plus) and m (minus) but marked the widespread adoption of compact symbols between operands in European texts.[12]
Standardization of infix notation in algebra occurred in the late 16th and 17th centuries through the works of François Viète and René Descartes. Viète, in his 1591 publication In artem analyticam isagoge, pioneered systematic literal notation by using vowels for unknowns (e.g., A) and consonants for known quantities (e.g., B, Z), arranging them in infix form with abbreviated words for operations, such as A³ + B²A = B²Z to represent cubic equations while enforcing homogeneity of dimensions. Descartes further refined this in La Géométrie (1637), consistently employing + and − signs, letters near the end of the alphabet (e.g., x, y, z) for unknowns, and superscripts for exponents (e.g., a²), enabling fully symbolic infix equations like x² + 2xy + y² = z² that integrated algebra with geometry. These advancements transformed infix notation from ad hoc abbreviations to a rigorous, universal framework.[13][14]
This period witnessed a broader transition in European mathematics from verbose rhetorical descriptions—common in medieval and ancient treatises—to concise symbolic infix expressions, enabling complex manipulations and influencing subsequent algebraic developments. In the 18th century, Gottfried Wilhelm Leibniz introduced notations for exponentiation (such as a^b) and early integral symbols, while Leonhard Euler further standardized infix forms for powers, functions, and calculus, solidifying its use in advanced mathematics.[3][15]
Adoption in Computing
In the late 1940s and early 1950s, early stored-program computers such as the EDSAC (1949) and UNIVAC I (1951) presented significant challenges for handling infix notation due to their reliance on low-level machine code and assembly languages. Programmers had to manually decompose mathematical expressions into sequential instructions, using subroutines for basic arithmetic operations like addition and multiplication, without any automated parsing of infix forms; this approach was labor-intensive and error-prone, limiting the complexity of expressions that could be efficiently implemented.[16]
A breakthrough came in 1954 with the Laning and Zierler system for the Whirlwind computer, the first operational algebraic compiler that accepted mathematical formulas in infix notation, translating them into machine code for guidance computations; however, it had limitations, such as restricted support for operator precedence and no handling of nested expressions beyond basic parentheses.[17] This system highlighted the parsing difficulties of infix notation on resource-constrained hardware, where ad hoc methods like string substitution were often employed to manage associativity without full syntactic analysis.[18]
The release of FORTRAN I in 1957 by IBM revolutionized the adoption of infix notation in programming, standardizing its use for writing natural mathematical expressions in high-level code, complete with defined precedence rules for operators; this made complex algebraic computations accessible without manual breakdown, influencing subsequent languages and compilers.[19] In calculator design, Hewlett-Packard's HP-35 (1972) initially employed postfix notation to simplify evaluation on limited hardware, avoiding the need for a full infix parser, but later models like the HP-27S (1988) transitioned to algebraic infix entry to better match user expectations from traditional mathematics, incorporating equation-solving capabilities.[20]
From the 1960s onward, advancements in compiler technology addressed infix parsing challenges through methods like recursive descent parsers, which recursively process grammar rules to build syntax trees for expressions. A key contribution was Edgar T. Irons' 1961 syntax-directed compiler for ALGOL 60, which used a table-driven approach with priority tables to handle operator precedence and parse infix expressions, integrating semantic actions for code generation; this approach became widely adopted in compilers for its simplicity and adaptability to context-free grammars.[21]
Applications
In Arithmetic and Algebra
Infix notation serves as the standard representation for arithmetic operations in mathematics, positioning the operator between two operands to express computations intuitively. Basic operations such as addition (+), subtraction (-), multiplication (\times or \cdot), and division (\div or /) are routinely written this way; for instance, the expression $5 + 3 \times 2 evaluates to $11$, as multiplication holds higher precedence than addition, requiring evaluation from left to right among operations of equal priority.[1] This notation facilitates everyday calculations, allowing users to directly interpret and perform mental or written arithmetic without additional conversion steps.[22]
In algebraic contexts, infix notation enables the formulation and manipulation of equations involving variables and constants, promoting clarity in symbolic reasoning. A common example is the linear equation $2x + 3 = 7, solved by isolating the variable: subtract $3from both sides to obtain2x = 4, then divide by $2 to yield x = 2. Such expressions rely on the notation's familiarity to balance terms and apply inverse operations systematically, forming the basis for solving systems in introductory algebra.[22]
Exponents and roots integrate seamlessly into infix notation, extending its utility to polynomial and radical expressions. For example, x^2 + y denotes a quadratic expression where the exponent $2applies toxbefore addition, often arising in formulas for area or distance.[22] Roots are similarly handled, as in\sqrt{x}for the principal square root, which can be rewritten asx^{1/2}$ to align with exponential form while maintaining the infix structure.
A frequent pitfall in using infix notation without explicit parentheses arises from overlooking precedence rules, leading to misinterpretation of operator order. Consider $1 + 2 \times 3, which correctly equals $7(multiplication first:2 \times 3 = 6, then 1 + 6 = 7), but could be erroneously computed as (1 + 2) \times 3 = 9if addition is prioritized.[1] Parentheses resolve such ambiguities, as in(1 + 2) \times 3$, ensuring precise evaluation in manual computations.[22]
In Programming and Calculators
In programming languages, infix notation is the standard for expressing operations, where operators are placed between operands, and parsing is handled through built-in precedence rules or user-defined mechanisms like operator overloading. In C++, operator overloading allows developers to define custom behavior for infix operators such as + or * for user-defined types, enabling intuitive infix expressions like a + b where a and b are objects of a complex number class, by implementing functions like operator+. Similarly, Python supports infix notation via special methods in its data model, such as __add__ for the + operator, which permits classes like vectors to use infix syntax (e.g., vec1 + vec2) while the interpreter parses according to operator precedence.[23]
Calculators commonly implement infix notation for user input to mimic mathematical writing, with internal evaluation engines that apply order of operations. For instance, the TI-84 Plus series accepts infix expressions directly on the home screen, such as 2 + 3 * 4, evaluating them to 14 by respecting precedence (multiplication before addition) without requiring postfix conversion from the user.[24]
To handle ambiguity in infix expressions, compilers and integrated development environments (IDEs) often issue warnings or errors, prompting the use of parentheses for clarification. In Microsoft Visual C++, compiler warning C4554 flags potential precedence issues in expressions like a & b == c, recommending parentheses (e.g., a & (b == c)) to resolve interpretation.[25] The GNU Compiler Collection (GCC) similarly warns about omitted parentheses in contexts where they affect evaluation, such as assignments mistaken for comparisons, enforcing explicit grouping to avoid unintended results.[26]
Many systems employ hybrid approaches for efficient evaluation, converting infix input to postfix notation internally using algorithms like the shunting-yard algorithm, developed by Edsger W. Dijkstra in 1961. This stack-based method processes infix tokens from left to right, outputting operands immediately and managing operators via a stack based on precedence, producing postfix form (e.g., converting a + b * c to a b c * +) for straightforward stack evaluation without recursion.[27]
Prefix Notation
Prefix notation, also known as Polish notation, is a syntactic form in which an operator precedes its operands. In this system, binary operators are placed before the two operands they connect, and unary operators precede their single operand, eliminating the need for parentheses to denote grouping. For instance, the expression for adding 2 and 3 is written as + 2 3, and negation of a variable p as N p.[28]
This notation was invented by the Polish logician Jan Łukasiewicz in the early 1920s as a tool for formal logic, with its first documented use appearing in his 1929 book Elements of Mathematical Logic. Łukasiewicz developed it during lectures at the University of Warsaw to represent logical operations without ambiguity, such as implication (C for "if...then") in expressions like C p q. Unlike conventional infix notation, where operators appear between operands, prefix notation reverses this order to prioritize the operator.[28]
A simple conversion from infix to prefix illustrates the transformation: the infix expression a + b becomes + a b in prefix form, while a more complex one like (a + b) * c converts to * + a b c. This restructuring fully encodes the order of operations directly in the sequence of symbols.[29]
One key advantage of prefix notation is its unambiguous parsing, as the position of the operator inherently defines the scope and precedence without requiring additional rules or parentheses. This simplifies evaluation in logical and computational contexts, reducing errors in complex expressions and facilitating machine processing.
Postfix Notation
Postfix notation, also known as reverse Polish notation, is a mathematical notation in which operators follow their operands, eliminating the need for parentheses to specify order of operations. For instance, the infix expression $2 + 3 is written in postfix as $2\ 3\ +. This structure allows expressions to be unambiguously parsed from left to right.[31][32]
A common application involves converting infix expressions to postfix form. Consider the infix expression a \times (b + c): it is transformed to postfix as a\ b\ c\ +\ \times, where the addition is performed first on b and c, and the result is then multiplied by a. This conversion follows a systematic algorithm using a stack to handle operator precedence and parentheses.[33][34]
Postfix notation is well-suited for stack-based evaluation, a process where operands are pushed onto a stack as they are encountered, and operators pop the necessary operands, compute the result, and push it back onto the stack. This approach enables efficient, iterative computation without recursive calls or explicit precedence rules. It is prominently used in the Forth programming language, which relies on postfix syntax and stack operations for all expressions and control flow.[35][36][37]
The notation was developed in the 1950s by Arthur W. Burks, Don W. Warren, and Jesse B. Wright to facilitate computation in early electronic machines, as outlined in their analysis of a parenthesis-free logical machine. Their work demonstrated how postfix enables compact representation and straightforward hardware implementation for arithmetic and logical operations.[38][39]
Parsing and Evaluation
Order of Operations
Infix notation relies on established conventions to resolve ambiguities in expressions containing multiple operators, ensuring consistent evaluation across mathematical contexts. These conventions, often summarized by the mnemonic PEMDAS (Parentheses, Exponents, Multiplication and Division, Addition and Subtraction) in the United States, dictate that operations are performed in a specific sequence: first within parentheses (or brackets), then exponents (or orders), followed by multiplication and division from left to right, and finally addition and subtraction from left to right.[40] An equivalent mnemonic, BODMAS (Brackets, Orders, Division and Multiplication, Addition and Subtraction), is commonly used in the United Kingdom and other regions, reflecting the same underlying rules but with terminology adjusted for local preferences.[41]
To illustrate, consider the infix expression $2 + 3 \times 4^2. Evaluation proceeds as follows: first compute the exponent $4^2 = 16; then the multiplication $3 \times 16 = 48; and finally the addition $2 + 48 = 50.[42] This step-by-step process highlights how precedence levels prevent misinterpretation, such as treating the expression as (2 + 3) \times 4^2 = 80, which would violate the conventions.
A key aspect of these conventions is left-to-right associativity for operators of equal precedence, which resolves ties without additional parentheses. For instance, in $20 \div 4 \times 3, division and multiplication share precedence, so evaluate left to right: $20 \div 4 = 5, then $5 \times 3 = 15, rather than $20 \div (4 \times 3) = 20 \div 12 \approx 1.67.[2] Similarly, $10 - 3 + 2 becomes (10 - 3) + 2 = 9, not $10 - (3 + 2) = 5.
While arithmetic expressions uniformly adopt left-to-right associativity, variations exist in other fields; for example, in mathematical logic, the implication operator (\to or \Rightarrow) is conventionally right-associative, parsing a \to b \to c as a \to (b \to c).[43] Related notations like prefix and postfix avoid such precedence rules altogether by positioning operators unambiguously relative to operands.
Precedence and Associativity
In infix notation, operator precedence determines the order in which operators are evaluated when multiple operators appear in an expression without parentheses, with higher-precedence operators binding more tightly to their operands. Associativity resolves ambiguities when operators of equal precedence are encountered, specifying whether they group from left to right or right to left. These rules are essential for unambiguously constructing the parse tree of an expression, ensuring consistent interpretation across mathematical and computational contexts.[44][45]
The standard precedence hierarchy for common arithmetic operators in infix expressions follows the conventions of PEMDAS (Parentheses, Exponents, Multiplication/Division, Addition/Subtraction), where exponents have the highest precedence among binary operators, followed by multiplication and division (equal precedence), and addition and subtraction (lowest, equal precedence). This hierarchy is depicted in the table below, listing operators from highest to lowest precedence (excluding parentheses, which always have the highest effective precedence).
This hierarchy ensures that, for instance, in the expression a + b \times c, the multiplication is performed before addition, forming the subtree b \times c first in the parse tree.[44]
Associativity applies when multiple operators of the same precedence are chained. Most arithmetic operators are left-associative, meaning they group from left to right; for example, a - b - c parses as (a - b) - c, creating a left-leaning parse tree where the left subtraction is evaluated first. Exponentiation, however, is typically right-associative, so a ^ b ^ c parses as a ^ (b ^ c), forming a right-leaning tree that evaluates the right exponentiation first. This distinction prevents ambiguities in chained operations and aligns with mathematical conventions for non-commutative operators like subtraction and division.[44][45]
The interplay of precedence and associativity directly influences parse tree construction. Consider the expression a / b * c: since division and multiplication share the same precedence level and are left-associative, it parses as (a / b) * c. The parse tree has division as the root of the left subtree, with multiplication as the overall root, binding a to b first before multiplying by c. If associativity were right instead, it would parse as a / (b * c), altering the tree structure and result, but the standard left associativity ensures predictable left-to-right evaluation for multiplicative operators.[44][45]
Unary operators, such as the unary minus (negation), are assigned higher precedence than binary arithmetic operators to treat them as modifiers of single operands. For example, in -a + b, the unary minus binds tightly to a, parsing as (-a) + b and forming a subtree for the negation before the addition. This elevated precedence distinguishes unary minus from binary subtraction, preventing incorrect groupings like -(a + b) in such contexts and maintaining the integrity of term-level negations in the overall parse tree.[45]