Try our Free Online Math Solver!

Thank you for visiting our site! You landed on this page because you entered a search term similar to this: explanation of how to simplify expressions containing parentheses.We have an extensive database of resources on explanation of how to simplify expressions containing parentheses. Below is one of them. If you need further help, please take a look at our software "Algebrator", a software program that can solve any algebra problem you enter!
8.11 Varieties of Syntax
So far, we have mostly considered expressionsin "infix form", i.e. ones which place binary (i.e.twoargument) operators between expressions for the operands. Aswe have discussed, parentheses, implied precedence, and groupingare used to resolve ambiguity. Examples are
A + B
A + B * C
(A + B) * C
A  B  C
There are several other types of syntax thatoccur either in isolation or in combination with the types wehave studied already. These are mentioned briefly in thefollowing sections.
Prefix syntax
Prefix syntax puts the operator before thearguments. It is used in many languages for userdefinedfunctions, e.g.
f(A, B, C).
The equivalent of the preceding list ofexpressions in prefix syntax would be:
+(A, B)
+(A, *(B, C))
*(+(A, B), C)
((A, B), C)
Expressions in the Prolog language usingarithmetic operators can be written in either infix or postfix.
Parenthesisfree Prefix Syntax
This is like prefix syntax, except that noparentheses or commas are used. In order for this form of syntaxto work without ambiguity, the arity (number of arguments)of each operator must be fixed. For example, we could not use as both unary minus and binary minus. The running set ofexpressions would appear as
+ A B
+ A * B C
* + A B C
  A B C
Parenthesisfree prefix syntax is used in theLogo language for userdefined procedures.
Postfix and Parenthesisfree Postfix
This is like prefix, except the operator comesafter the arguments. It is most usually seen in theparenthesisfree form, where it is also called RPN (reversePolish notation).
(A, B)+ A B +
(A, (B, C)*)+ A B C * +
((A, B)+, C)* A B + C *
((A, B), C) A B  C 
The parenthesisfree version of this syntaxalso requires the property that each operator must be of fixedarity.
S Expression Syntax
A grammar for S expressions was presentedearlier. The notion of S expressions provide a syntax which,despite its initially foreign appearance, has several advantages:
The arity of operators need not be fixed. Forexample, we could use a + operator that has any number ofarguments, understanding the meaning to be compute the sum ofthese arguments. [For that matter, prefix and postfix withparentheses required also have this property.]
The number of symbols is minimal and a parsingprogram is therefore relatively easy to write.
In Sexpression syntax, expressions are of theform
( operator argument1 argument2.... argumentN )
where the parentheses are required.Sexpressions are therefore a variant on prefix syntax. SometimesSexpressions are called "Cambridge Polish" in honor ofCambridge, Mass., the site of MIT, the place where the languageLisp was invented. Lisp uses Sexpression syntax exclusively.
In S expressions, additional parenthesescannot be added without changing the meaning of the expression.Additional parentheses are never necessary to remove ambiguitybecause there is never any ambiguity: every operator has its ownpair of parentheses.
Example: Arithmetic Expressions in SExpression Syntax
( + A B)
( + A ( * B C ) )
( * (+ A B) C)
(  (  A B ) C )
S expressions are not only for arithmeticexpressions; they can be used for representing many forms ofstructured data, such as heterogeneous lists. For example, theheterogeneous list used in an earlier rex example
[ my_dir,
mail,
[ archive, old_mail, older_mail],
[ projects,
[ sorting, quick_sort, heap_sort],
[ searching, depth_first, breadth_first]
],
[games, chess, checkers, tictactoe]
]
could be represented as the following Sexpression
( my_dir
( archive old_mail older_mail)
( projects
( sorting quick_sort heap_sort)
( searching depth_first breadth_first)
)
(games chess checkers tictactoe)
)
S expressions are, in many ways, ideal forrepresenting languages directly in their abstract syntax. Thesyntax is extremely uniform. Moreover, given that we have areader for S expressions available, we don't need any otherparser. We can analyze a program by taking the S expression apartby recursive functions. This is the approach taken in thelanguage Lisp. Every construct in the language can play the roleof an abstract syntax constructor. This constructor is identifiedas the first argument in a list. The other arguments of theconstructor are the subsequent items in the list.
We saw above how arithmetic expressions arerepresented with S expressions. Assignment in Lisp is representedwith the setq constructor:
(setq Var Expression )
sets the value of variable Var to thatof expression Expression. A twoarmed conditional isrepresented by a list of four elements:
(if Condition Tbranch Fbranch)
and function definitions are represented by theconstructor defun. For example, the following is afactorial program in Lisp:
(defun factorial (N)
(if ( < N 1 )
0
(* N (factorial ( N 1) ) ) ) )
In the next major section, we give examples ofextendible interpreters which exploit the S expression syntax.
Superscript or Subscript Syntax
Some mathematics occasionally texts use, forexample,
x^{f}
to denote the application of function f to x.Due to the usual onedimensional nature of character strings, wedo not often go out of our way to use this in computer science.
ExpressionTree Syntax
Expression trees are trees in which the leavesare labeled with variables or constants and the interior nodesare labeled with operators. The subtrees of an operator noderepresent the argument expressions. The advantage of trees isthat it allows us to visualize the flow of values that wouldcorrespond to the evaluation of an expression. These correspondclosely to the abstract syntax trees discussed earlier.
Reading clockwise from upperleft, theexpressiontree syntax
for the equivalents of infix A+B,A+(B*C), (A+B)*C, and (AB)C.
DAG (Directed Acyclic Graph) Syntax
DAG syntax is an extension of expressionteesyntax in which the more general concept of a DAG (Directed,Acyclic, Graph) is used. The added benefit of DAGs is thatsharing of common subexpressions can be shown. For example, in
(A + B) * C + D / (A + B)
we might want to indicate that thesubexpression A + B is one and the same. This would be shown byhaving two arcs leaving the node corresponding to A + B:
DAG for an arithmetic expression
DAG syntax is a subset of what is used indataflow languages. Typically the latter allow loops as well,assuming that an appropriate semantics can be given to a loop,and are therefore not confined to DAGs (they can be cyclic). Atypical example of languages that make use of loops are those forrepresenting signalflow graphs, as occur in digital signalprocessing.
Graphical syntax for a digital filter
In the jargon of digital filters, a filter withloops is called "recursive".
The Spreadsheet Model
The spreadsheet model is a relativelyuserfriendly computing model that implicitly employs DAGs torepresent computations. In a spreadsheet, the computationalframework is represented in a twodimensional array of cells.Each cell contains either a primitive data value, such as aninteger or string, or an expression. An expression is typicallyan arithmetic or functional expression entailing operators andthe names of other cells as variables. The spreadsheet systemcomputes the values in cells containing expressions, and displaysthe value in the cell itself. Whenever the user changes one ofthe primitive data values in its cell, the relevant cellscontaining expressions are changed by the system to reflect thenew value. The underlying mechanism is that of a DAG, where somearcs are identified with cells.
For simplicity, consider a 2 x 3 spreadsheet,as shown below. The cells in the spreadsheet are designated A1,A2, A3, B1, B2, B3.
1  2  3  
A  B1 * B2 + B3 / B1  value of A  value of B 
B  A2 + A3  value of C  value of D 
A simple spreadsheet representable as a DAG
Cell A1 of this spreadsheet represents thevalue of the previous DAG expression, if we associate the valuesA, B, C, and D with A2, A3, B2, and B3 respectively. Theexpression in cell B1 represents the common subexpression shownin the DAG.
Typical states of the spreadsheet, with valuesentered by the user for A, B,C, and D, would show as follows:
1  2  3  
A  32.75  3  5 
B  8  4  6 
1  2  3  
A  50.7  4  6 
B  10  5  7 
Two different states of the simplespreadsheet
Exercises
1 Give unambiguous grammarsfor representing arithmetic expressions with operators + and *:
(a) In postfix form
(b) In prefix form
(c) In Sexpression form
2 Build an evaluator forexpressions in postfix form. Although it could be done withrecursion, such an evaluator is typically described using a"stack" data structure which retains operand values.Values are removed in the order of their recency of insertion:
When an operand is scanned, it is pushed on thestack.
When an operator is scanned, the appropriatenumber of arguments is removed from the stack, the operator isapplied, and the result pushed on the stack.
Such is the principle on which RPN calculatorswork. It is also the basis of the FORTH language, and thePostScript language which is built on FORTH syntax.
3 Build an evaluator forexpressions in postfix form which uses no explicit stack. (Animplicit stack is used in the recursive calls in this evaluator).[Hint: This can be done by defining recursive functions havingarguments corresponding to the top so many values on the stack,e.g. there would be three functions, assuming at most 2aryoperators). When such a function returns, it corresponds tohaving used those two arguments.]
4 Having done the preceding twoproblems, discuss tradeoffs of the two versions with respect toprogram clarity, tail recursion, space efficiency, etc.
5 Build an evaluator forexpressions in prefix form.
6 Devise anexpressionbased language for specifying graphics. Develop atranslator which produces PostScript. Display the results on alaser printer or workstation screen.
7 Develop aspreadsheet calculator, including a means of parsing theexpressions contained within formula cells.
8 Explore theergonomics of copying formulas in cells, as are done incommercial spreadsheet implementations. After devising a goodexplanation (or a better scheme), implement your ideas.
9 Implement a systemsimplifying arithmetic expressions involving the operators +, ,*, /, and exp (exponent) with their usual meanings. Forconvenience, use S expression input syntax, wherein eachexpression is either:
A numeric constant
An atom, representing a variable
A list of the form (Op E1 E2), where E1 and E2are themselves expressions and Op is one of the four operators.
The kinds of operations involved insimplification would include:
removing superfluous constants such as 1's and0's:
(+ E1 0)_1 E1
(* E1 1)_1 E1
carrying out special cases of the operatorssymbolically:
( E1 E1)_1 0
(exp E 0)_1 1
eliminating / in favor of *:
(/ (/ A B) C)_1 (/ A (* B C))
etc.
For example, if your system is given the inputexpression
(/ (/ A (* B ( C C)) D)
it would produce
(/ A (* B D))
These kinds of simplifications are includedautomatically in computer algebra systems such asMathematica™ and Maple, which have a programming languagecomponent. However, the user is usually unable to customize, inan easy way, the transformations to suit special purposes.
10 Implement a systemin the spirit of the previous exercise, except includetrigonometric identities.
11 Implement a systemin the spirit of the previous exercise, except include integralsand derivatives.