Evaluating Algebraic Expressions
Thumrongsak Kosiyatrakul
Thumrongsak Kosiyatrakul
Evaluating Algebraic Expressions
Process Algebraic Expressions
Imagine writing a program that evaluates algebraic expressions Users can enter a string representing algebraic expression such as
(5 + 2 ∗ 3) − 4 / 10 ∗ 4 + (2 − 3) 9 + 12 − 2 ∗ 3 − 4 / 10 ∗ 4
12 ∗ 3 ∗ 2 / 9 + 10 − (10 + 2) ∗ 4
The program must evaluate expressions based on Operator precedence
Left/Right associations Parentheses
Evaluating Algebraic Expressions
Thumrongsak Kosiyatrakul
First Step
An algebraic expression consists of
Operands: 12, 44, and 30 (integers for simplicity) Operators: +, −, ∗, and /
Delimiters: (), [], and {}
Whitespaces: spaces
Given a string representation of an algebraic expression, how to turn it into a list of strings of operands, operators, and delimiters? Examples:
“(12 + 2) * 3” { [“(“,”12″,”+”,”2″,”)”,”*”,”3″]
“2*(3 + 4)” { [“2″,”*”,”(“,”3″,”+”,”4″,”)”] “32” { [“32”]
“(54 +” { [“(“,”54″,”+”]
Answer: it is your homework
Evaluating Algebraic Expressions
Thumrongsak Kosiyatrakul
Computer Science Tutoring
Checking for Balanced Delimiters
A balanced expression contains delimiters that are paired correctly
Examples (balanced expressions):
(2 + 9) − 3
2 − [10 ∗ (3 / 2)] + 4
{2 − [20 ∗ (4 − 9)]} ∗ (5 + (33 − 2))
Examples (unbalanced expressions): [2+(3∗2]−7): Donotmatch
10 ∗ (8 + (4 / 9): Not enough right parenthesis 10 + (12 − 9)) ∗ 2: Not enough left parenthesis (13 + 9)) + (2: Parentheses out of order
Evaluating Algebraic Expressions
Thumrongsak Kosiyatrakul
Checking for Balanced Delimiters
How can we check whether an expression is balanced? By eyes: Let’s try
(𝑎+(𝑏+(𝑐+𝑑)+𝑒)+ 𝑓) 𝑎+(𝑏+(𝑐+𝑑))+(𝑒+ 𝑓) (𝑎 + 𝑏) + (𝑐 + (𝑑 + 𝑒)
𝑎 + (𝑏 + (𝑐 + 𝑑)))
𝑎 + (𝑏 + 𝑐)) + (𝑑 + 𝑒 Notice that
we try to remember/count left/open parentheses
when we found a right/close parenthesis, we try to match it with the one we remember
Generally, we use a stack to store left parentheses Different types are supported, (), [], and {}
Let’s try again using a stack
Evaluating Algebraic Expressions
Thumrongsak Kosiyatrakul
Unbalance Expressions using Stack
The right parenthesis does not match the left parenthesis on top of the stack
The right is ) but the top of the stack is not a left The right is ] but the top of the stack is either ( or }
The right parenthesis does not have any left parenthesis to match with (stack is empty)
When we reach the end of the expression, there are left parentheses left in the stack
Evaluating Algebraic Expressions
Thumrongsak Kosiyatrakul
程序代写 CS代考 加微信: cstutorcs
Infix and Postfix Expression
Infix expression: An operator is in between two operands 2+5
10 ∗ (12 − 3)
Postfix expression: An operator is located after two operands:
25+ 10123 − ∗
Postfix expressions are simpler to process no precedence rules,
no left/right associations, and no parenthesis
When a postfix expression is constructed, operator precedence, left/right associations, and parentheses, are used already
𝑎+𝑏∗𝑐{𝑎𝑏𝑐∗+ (𝑎 + 𝑏) ∗ 𝑐 { 𝑎 𝑏 + 𝑐 ∗
Evaluating Algebraic Expressions
Thumrongsak Kosiyatrakul
Transforming an Infix Expression to a Postfix Expression
Pencil and Paper Method:
1 Parenthesized infix expression to remove operator precedence
2 Move each operator to the right until it is next its associated close
parenthesis
3 Remove parentheses
Example: (𝑎 + 𝑏) ∗ 𝑐
1 ((𝑎+𝑏)∗𝑐)
2 ((𝑎𝑏+)𝑐∗)
Exercise: Turn these infix expressions into postfix expressions
𝑎 ∗ 𝑏 / (𝑐 − 𝑑) 𝑎 / 𝑏 + (𝑐 − 𝑑) 𝑎/𝑏+𝑐−𝑑
Evaluating Algebraic Expressions
Thumrongsak Kosiyatrakul
Evaluate Postfix Expressions
Recallthepostfixexpressionof((𝑎+𝑏)∗𝑐)is𝑎𝑏 + 𝑐∗ To evaluate a postfix expression:
Start of the left until you find an operator
Use two numbers on the left the the operator as operands Evaluate that sub-expression and replace the two numbers and the operator by the result
Keep on doing this until you end up with a single number
Let’s try 12 / 6 + (5 − 2)
Put parentheses and you get ((12 / 6) + (5 − 2)) and you know
the result is 5.
Move operators until it reach its corresponding left parentheses and you get ((12 6 /) (5 2 −) +) Thepostfixexpressionis126/52 − +
Replace126/by2andyouget252 − + Replace 5 2 − by 3 and you get 2 3 + Replace 2 3 + by 5 and you are done
Evaluating Algebraic Expressions
Thumrongsak Kosiyatrakul
Evaluate Postfix Expressions
Notice that we kind of use a stack again. How? Start from left, if it is a number, push it to the stack
If it is an operator, pop the top two from the stack as operands Push result back to the stack
Keep doing this until you reach the end. The result is at the top of the stack
Try some more but use stack this time 1+2−3+4−5
((((1 + 2) − 3) + 4) − 5) ((((1 2 +) 3 −) 4 +) 5 −) 12+3−4+5− 33−4+5−
How do we convert from a infix to a postfix expression in computer?
Evaluating Algebraic Expressions
Thumrongsak Kosiyatrakul
Infix to Postfix Conversion
Consider the following infix and postfix expression
𝑎+𝑏−𝑐≡𝑎𝑏+𝑐−
𝑎 + (𝑏 − 𝑐) ≡ 𝑎 𝑏 𝑐 − + 𝑎+𝑏∗𝑐≡𝑎𝑏𝑐∗+ (𝑎 + 𝑏) ∗ 𝑐 ≡ 𝑎 𝑏 + 𝑐 ∗ 𝑎 ∗ 𝑏 + 𝑐 ≡ 𝑎 𝑏 ∗ 𝑐+
𝑎 ∗ (𝑏 + 𝑐) ≡ 𝑎 𝑏 𝑐 + ∗
Note that the order of variable names does not change in any cases
They always start with 𝑎, follows by 𝑏, and follows by 𝑐 Only the order and positions of operators were changed
Operators that are needed to be used earlier stay on the left side of the operators that are needed to be used later
The order of operations depend on operator precedence, left/right associations, and parentheses
We cannot put an operator into an postfix expression until we know what is the next operator (also depends on parentheses)
Evaluating Algebraic Expressions
Thumrongsak Kosiyatrakul
Infix to Postfix Conversion
To convert an infix expression to a postfix expression, always push an open parenthesis onto the stack and treat them as an operator with the lowest precedence
What to Do
Operator +, −, ∗, or /
Open parenthesis Close parenthesis
Append each operand to the end of the output expression.
Pop operators from the stack, appending them to
the output expression, until the stack is empty or
its top entry has a lower precedence than the new operator. Then push the new operator onto the stack.
Push ( onto the stack.
Pop operators from the stack and append them to the output expression until an open parenthesis is popped. Discard both parentheses.
Evaluating Algebraic Expressions
Thumrongsak Kosiyatrakul
Programming Help, Add QQ: 749389476
Exercise: Infix to Postfix Conversion
𝑎 / 𝑏 ∗ (𝑐 + (𝑑 − 𝑒))
Next Characters from Infix Expression
Postfix Form
Operator Stack (bottom to top)
+ ( 𝑑 − 𝑒 )
𝑎𝑏/𝑐𝑑 𝑎𝑏/𝑐𝑑 𝑎𝑏/𝑐𝑑𝑒 𝑎𝑏/𝑐𝑑𝑒− 𝑎𝑏/𝑐𝑑𝑒− 𝑎𝑏/𝑐𝑑𝑒−+ 𝑎𝑏/𝑐𝑑𝑒−+ 𝑎𝑏/𝑐𝑑𝑒−+∗
∗(+ ∗(+( ∗(+( ∗(+(− ∗(+(− ∗(+( ∗(+
Evaluating Algebraic Expressions
Thumrongsak Kosiyatrakul