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.two-argument) 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 user-definedfunctions, 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.
Parenthesis-free 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
Parenthesis-free prefix syntax is used in theLogo language for user-defined procedures.
Postfix and Parenthesis-free Postfix
This is like prefix, except the operator comesafter the arguments. It is most usually seen in theparenthesis-free 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 parenthesis-free 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 S-expression syntax, expressions are of theform
( operator argument-1 argument-2.... argument-N )
where the parentheses are required.S-expressions are therefore a variant on prefix syntax. SometimesS-expressions are called "Cambridge Polish" in honor ofCambridge, Mass., the site of MIT, the place where the languageLisp was invented. Lisp uses S-expression 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, tic-tac-toe]
]
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 tic-tac-toe)
)
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 two-armed conditional isrepresented by a list of four elements:
(if Condition T-branch F-branch)
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,
xf
to denote the application of function f to x.Due to the usual one-dimensional nature of character strings, wedo not often go out of our way to use this in computer science.
Expression-Tree Syntax
Expression trees are trees in which the leavesare labeled with variables or constants and the interior nodesare labeled with operators. The sub-trees 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 upper-left, theexpression-tree syntax
for the equivalents of infix A+B,A+(B*C), (A+B)*C, and (A-B)-C.
DAG (Directed Acyclic Graph) Syntax
DAG syntax is an extension of expression-teesyntax in which the more general concept of a DAG (Directed,Acyclic, Graph) is used. The added benefit of DAGs is thatsharing of common sub-expressions can be shown. For example, in
(A + B) * C + D / (A + B)
we might want to indicate that thesub-expression 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 signal-flow 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 relativelyuser-friendly computing model that implicitly employs DAGs torepresent computations. In a spreadsheet, the computationalframework is represented in a two-dimensional 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 sub-expression 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 S-expression 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 2-aryoperators). 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 anexpression-based 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.