[ACCEPTED]-conversion from infix to prefix-notation
Algorithm ConvertInfixtoPrefix
Purpose: Convert an infix expression into a prefix expression. Begin
// Create operand and operator stacks as empty stacks.
Create OperandStack
Create OperatorStack
// While input expression still remains, read and process the next token.
while( not an empty input expression ) read next token from the input expression
// Test if token is an operand or operator
if ( token is an operand )
// Push operand onto the operand stack.
OperandStack.Push (token)
endif
// If it is a left parentheses or operator of higher precedence than the last, or the stack is empty,
else if ( token is '(' or OperatorStack.IsEmpty() or OperatorHierarchy(token) > OperatorHierarchy(OperatorStack.Top()) )
// push it to the operator stack
OperatorStack.Push ( token )
endif
else if( token is ')' )
// Continue to pop operator and operand stacks, building
// prefix expressions until left parentheses is found.
// Each prefix expression is push back onto the operand
// stack as either a left or right operand for the next operator.
while( OperatorStack.Top() not equal '(' )
OperatorStack.Pop(operator)
OperandStack.Pop(RightOperand)
OperandStack.Pop(LeftOperand)
operand = operator + LeftOperand + RightOperand
OperandStack.Push(operand)
endwhile
// Pop the left parthenses from the operator stack.
OperatorStack.Pop(operator)
endif
else if( operator hierarchy of token is less than or equal to hierarchy of top of the operator stack )
// Continue to pop operator and operand stack, building prefix
// expressions until the stack is empty or until an operator at
// the top of the operator stack has a lower hierarchy than that
// of the token.
while( !OperatorStack.IsEmpty() and OperatorHierarchy(token) lessThen Or Equal to OperatorHierarchy(OperatorStack.Top()) )
OperatorStack.Pop(operator)
OperandStack.Pop(RightOperand)
OperandStack.Pop(LeftOperand)
operand = operator + LeftOperand + RightOperand
OperandStack.Push(operand)
endwhile
// Push the lower precedence operator onto the stack
OperatorStack.Push(token)
endif
endwhile
// If the stack is not empty, continue to pop operator and operand stacks building
// prefix expressions until the operator stack is empty.
while( !OperatorStack.IsEmpty() ) OperatorStack.Pop(operator)
OperandStack.Pop(RightOperand)
OperandStack.Pop(LeftOperand)
operand = operator + LeftOperand + RightOperand
OperandStack.Push(operand)
endwhile
// Save the prefix expression at the top of the operand stack followed by popping // the operand stack.
print OperandStack.Top()
OperandStack.Pop()
End
0
(a–b)/c*(d + e – f / g)
Prefix notation (reverse polish has the 3 operator last, it is unclear which one you 2 meant, but the principle will be exactly 1 the same):
(/ f g)(+ d e)(- (+ d e) (/ f g))(- a b)(/ (- a b) c)(* (/ (- a b) c) (- (+ d e) (/ f g)))
If there's something about what infix and 13 prefix mean that you don't quite understand, I'd 12 highly suggest you reread that section of your textbook. You aren't doing yourself 11 any favors if you come out of this with 10 the right answer for this one problem, but 9 still don't understand the concept.
Algorithm-wise, its 8 pretty darn simple. You just act like a 7 computer yourself a bit. Start by puting 6 parens around every calculation in the order 5 it would be calculated. Then (again in order 4 from first calculation to last) just move 3 the operator in front of the expression 2 on its left hand side. After that, you can 1 simplify by removing parens.
(a–b)/c*(d + e – f / g)
step 1: (a-b)/c*(d+e- /fg))
step 2: (a-b)/c*(+de - /fg)
step 3: (a-b)/c * -+de/fg
Step 4: -ab/c * -+de/fg
step 5: /-abc * -+de/fg
step 1 6: */-abc-+de/fg
This is prefix notation.
I saw this method on youtube hence posting 4 here.
given infix expression : (a–b)/c*(d 3 + e – f / g)
reverse it :
)g/f-e+d(*c/)b-a(
read 2 characters from left to right.
maintain 1 one stack for operators
1. if character is operand add operand to the output
2. else if character is operator or )
2.1 while operator on top of the stack has lower or **equal** precedence than this character pop
2.2 add the popped character to the output.
push the character on stack
3. else if character is parenthesis (
3.1 [ same as 2 till you encounter ) . pop ) as well
4. // no element left to read
4.1 pop operators from stack till it is not empty
4.2 add them to the output.
reverse the output and print.
credits : youtube
(a–b)/c*(d + e – f / g)
remember scanning 23 the expression from leftmost to right most start 22 on parenthesized terms follow the WHICH 21 COMES FIRST rule... *, /, % are on the same 20 level and higher than + and -.... so (a-b) = -bc 19 prefix (a-b) = bc- for postfix another parenthesized 18 term: (d + e - f / g) = do move the / first then 17 plus '+' comes first before minus sigh '-' (remember 16 they are on the same level..) (d + e - f 15 / g) move / first (d + e - (/fg)) = prefix (d 14 + e - (fg/)) = postfix followed by + then 13 - ((+de) - (/fg)) = prefix ((de+) - (fg/)) = postfix
(-(+de)(/fg)) = prefix 12 so the new expression is now -+de/fg (1) ((de+)(fg/)-) = postfix 11 so the new expression is now de+fg/- (2)
(a–b)/c* hence
(a-b)/c*(d 10 + e – f / g) = -bc prefix [-ab]/c*[-+de/fg] ---> taken 9 from (1) / c 8 * do not move yet so '/' comes first before 7 '*' because they on the same level, move 6 '/' to the rightmost : /[-ab]c * [-+de/fg] then 5 move '*' to the rightmost
- / [-ab]c[-+de/fg] = remove the grouping symbols = */-abc-+de/fg --> Prefix
(a-b)/c*(d + e 4 – f / g) = bc- for postfix [ab-]/c*[de+fg/-]---> taken 3 from (2) so '/' comes first before '' because they on the same level, move '/' to the leftmost: [ab-]c[de+fg/-]/ then 2 move '' to the leftmost [ab-] c [de+fg/-]/ = remove the grouping symbols= a 1 b - c d e + f g / - / * --> Postfix
simple google search came up with this. Doubt 17 anyone can explain this any simpler. But 16 I guess after an edit, I can try to bring 15 forward the concepts so that you can answer 14 your own question.
Hint :
Study for exam, hard, you 13 must. Predict you, grade get high, I do 12 :D
Explanation :
It's all about the way operations 11 are associated with operands. each notation 10 type has its own rules. You just need 9 to break down and remember these rules. If 8 I told you I wrote (2*2)/3 as [* /] (2,2,3) all 7 you need to do is learn how to turn the 6 latter notation in the former notation.
My 5 custom notation says that take the first 4 two operands and multiple them, then the 3 resulting operand should be divided by the 2 third. Get it ? They are trying to teach 1 you three things.
- To become comfortable with different notations. The example I gave is what you will find in assembly languages. operands (which you act on) and operations (what you want to do to the operands).
- Precedence rules in computing do not necessarily need to follow those found in mathematics.
- Evaluation: How a machine perceives programs, and how it might order them at run-time.
This algorithm will help you for better 17 understanding .
Step 1. Push “)” onto STACK, and 16 add “(“ to end of the A.
Step 2. Scan A from 15 right to left and repeat step 3 to 6 for 14 each element of A until the STACK is 13 empty.
Step 3. If an operand is encountered 12 add it to B.
Step 4. If a right parenthesis 11 is encountered push it onto STACK.
Step 5. If 10 an operator is encountered then: a. Repeatedly 9 pop from STACK and add to B each operator 8 (on the top of STACK) which has same or 7 higher precedence than the operator. b. Add 6 operator to STACK.
Step 6. If left parenthesis 5 is encontered then a. Repeatedly pop 4 from the STACK and add to B (each operator 3 on top of stack until a left parenthesis 2 is encounterd) b. Remove the left parenthesis.
Step 1 7. Exit
https://en.wikipedia.org/wiki/Shunting-yard_algorithm
The shunting yard algorithm can also be 10 applied to produce prefix notation (also 9 known as polish notation). To do this one 8 would simply start from the end of a string 7 of tokens to be parsed and work backwards, reverse 6 the output queue (therefore making the output 5 queue an output stack), and flip the left 4 and right parenthesis behavior (remembering 3 that the now-left parenthesis behavior should 2 pop until it finds a now-right parenthesis).
from collections import deque
def convertToPN(expression):
precedence = {}
precedence["*"] = precedence["/"] = 3
precedence["+"] = precedence["-"] = 2
precedence[")"] = 1
stack = []
result = deque([])
for token in expression[::-1]:
if token == ')':
stack.append(token)
elif token == '(':
while stack:
t = stack.pop()
if t == ")": break
result.appendleft(t)
elif token not in precedence:
result.appendleft(token)
else:
# XXX: associativity should be considered here
# https://en.wikipedia.org/wiki/Operator_associativity
while stack and precedence[stack[-1]] > precedence[token]:
result.appendleft(stack.pop())
stack.append(token)
while stack:
result.appendleft(stack.pop())
return list(result)
expression = "(a - b) / c * (d + e - f / g)".replace(" ", "")
convertToPN(expression)
step 1 through:
step 1 : token ) ; stack:[ ) ]
result:[ ]
step 2 : token g ; stack:[ ) ]
result:[ g ]
step 3 : token / ; stack:[ ) / ]
result:[ g ]
step 4 : token f ; stack:[ ) / ]
result:[ f g ]
step 5 : token - ; stack:[ ) - ]
result:[ / f g ]
step 6 : token e ; stack:[ ) - ]
result:[ e / f g ]
step 7 : token + ; stack:[ ) - + ]
result:[ e / f g ]
step 8 : token d ; stack:[ ) - + ]
result:[ d e / f g ]
step 9 : token ( ; stack:[ ]
result:[ - + d e / f g ]
step 10 : token * ; stack:[ * ]
result:[ - + d e / f g ]
step 11 : token c ; stack:[ * ]
result:[ c - + d e / f g ]
step 12 : token / ; stack:[ * / ]
result:[ c - + d e / f g ]
step 13 : token ) ; stack:[ * / ) ]
result:[ c - + d e / f g ]
step 14 : token b ; stack:[ * / ) ]
result:[ b c - + d e / f g ]
step 15 : token - ; stack:[ * / ) - ]
result:[ b c - + d e / f g ]
step 16 : token a ; stack:[ * / ) - ]
result:[ a b c - + d e / f g ]
step 17 : token ( ; stack:[ * / ]
result:[ - a b c - + d e / f g ]
# the final while
step 18 : token ( ; stack:[ ]
result:[ * / - a b c - + d e / f g ]
here is an java implementation for convert 2 infix to prefix and evaluate prefix expression 1 (based on rajdip's algorithm)
import java.util.*;
public class Expression {
private static int isp(char token){
switch (token){
case '*':
case '/':
return 2;
case '+':
case '-':
return 1;
default:
return -1;
}
}
private static double calculate(double oprnd1,double oprnd2,char oprt){
switch (oprt){
case '+':
return oprnd1+oprnd2;
case '*':
return oprnd1*oprnd2;
case '/':
return oprnd1/oprnd2;
case '-':
return oprnd1-oprnd2;
default:
return 0;
}
}
public static String infix2prefix(String infix) {
Stack<String> OperandStack = new Stack<>();
Stack<Character> OperatorStack = new Stack<>();
for(char token:infix.toCharArray()){
if ('a' <= token && token <= 'z')
OperandStack.push(String.valueOf(token));
else if (token == '(' || OperatorStack.isEmpty() || isp(token) > isp(OperatorStack.peek()))
OperatorStack.push(token);
else if(token == ')'){
while (OperatorStack.peek() != '(') {
Character operator = OperatorStack.pop();
String RightOperand = OperandStack.pop();
String LeftOperand = OperandStack.pop();
String operand = operator + LeftOperand + RightOperand;
OperandStack.push(operand);
}
OperatorStack.pop();
}
else if(isp(token) <= isp(OperatorStack.peek())){
while (!OperatorStack.isEmpty() && isp(token)<= isp(OperatorStack.peek())) {
Character operator = OperatorStack.pop();
String RightOperand = OperandStack.pop();
String LeftOperand = OperandStack.pop();
String operand = operator + LeftOperand + RightOperand;
OperandStack.push(operand);
}
OperatorStack.push(token);
}
}
while (!OperatorStack.isEmpty()){
Character operator = OperatorStack.pop();
String RightOperand = OperandStack.pop();
String LeftOperand = OperandStack.pop();
String operand = operator + LeftOperand + RightOperand;
OperandStack.push(operand);
}
return OperandStack.pop();
}
public static double evaluatePrefix(String prefix, Map values){
Stack<Double> stack = new Stack<>();
prefix = new StringBuffer(prefix).reverse().toString();
for (char token:prefix.toCharArray()){
if ('a'<=token && token <= 'z')
stack.push((double) values.get(token));
else {
double oprnd1 = stack.pop();
double oprnd2 = stack.pop();
stack.push(calculate(oprnd1,oprnd2,token));
}
}
return stack.pop();
}
public static void main(String[] args) {
Map dictionary = new HashMap<>();
dictionary.put('a',2.);
dictionary.put('b',3.);
dictionary.put('c',2.);
dictionary.put('d',5.);
dictionary.put('e',16.);
dictionary.put('f',4.);
dictionary.put('g',7.);
String s = "((a+b)/(c-d)+e)*f-g";
System.out.println(evaluatePrefix(infix2prefix(s),dictionary));
}
}
In Prefix expression operators comes first 3 then operands : +ab[ oprator ab ]
Infix : (a–b)/c*(d + e – f / g)
Step 1: (a - b) = (- ab) [ '(' has 2 highest priority ]
step 2: (d + e - f / g) = (d + e - / fg) [ '/' has highest 1 priority ]
= (+ de - / fg )
['+','-' has same priority but left to right associativity]
= (- + de / fg)
Step 3: (-ab )/ c * (- + de / fg) = / - abc * (- + de / fg)
= * / - abc - + de / fg
Prefix : * / - abc - + de / fg
Infix to PostFix using Stack:
Example: Infix--> P-Q*R^S/T+U *V
Postfix --> PQRS^*T/-UV
Rules:
Operand ---> Add it to postfix
"(" ---> Push it on the stack
")" ---> Pop and add to postfix all operators till 1st left parenthesis
Operator ---> Pop and add to postfix those operators that have preceded
greater than or equal to the precedence of scanned operator.
Push the scanned symbol operator on the stack
0
More Related questions
We use cookies to improve the performance of the site. By staying on our site, you agree to the terms of use of cookies.