Welcome back after a long time!!
@ UCSC for our data structures & algorithms course we had a assignment for converting between prefix-infix-postfix notations. So there are total of 6 conversions! I’m posting this because as i experienced this is a good project for get around in stacks, recursion and basic algorithm and data structure stuff.
I implemented four of conversions which are infix –> prefix,
infix –> postfix , prefix –> infix, postfix –> infix.
Other 2 conversions will happen using the above ones.
I wrote up the program that will support unary operators(minus numbers) 1-n digit numbers (5 , 50 , 456 , ..)
BELOW are the pseudocodes
Infix to Postfix algorithm
1) Check for parenthesis errors. If found return ERROR
2) Get the next element and store it in a variable – temp
a. IF temp is a operand, examine the next element
1. IF it is a operand output temp
2. ELSE IF stack.top is unary minus --> output temp
3. ELSE output temp and a SPACE
ii. ELSE IF stack.top is unary minus -->output temp
iii. ELSE output temp and a SPACE
b. ELSE IF temp is a opening parenthesis -->push stack with temp
c. ELSE IF temp is a operator
i. IF stack is empty -->push stack with temp
ii. ELSE IF stack.top is a opening parenthesis -->push stack with temp
iii. ELSE IF temp’s precedence > stack.top precedence -->push stack with temp
iv. ELSE output stack.pop and a SPACE AND repeat step “c”
d. ELSE IF temp is a closing parenthesis
i. WHILE stack.top is NOT opening parenthesis -->output stack.pop and a SPACE
ii. IF stack.top is opening parenthesis -->pop the stack
3) WHILE stack IS NOT empty -->output stack.pop and a SPACE
Infix to Prefix algorithm
Same as infix to postfix algorithm except,
1) Before step 2 the input string will be reversed.
2) Also the two parenthesis{ “ ( ” , ” ) ” } will be swapped where mentioned.
3) Lastly the output will be reversed
Prefix to Infix algorithm
This algorithm is a non-tail recursive method.
1) The reversed input string is completely pushed into a stack.
prefixToInfix(stack)
1) IF stack is not empty
a. Temp -->pop the stack
b. IF temp is a operator
i. Write a opening parenthesis to output
ii. prefixToInfix(stack)
iii. Write temp to output
iv. prefixToInfix(stack)
v. Write a closing parenthesis to output
c. ELSE IF temp is a space -->prefixToInfix(stack)
d. ELSE
i. Write temp to output
ii. IF stack.top NOT EQUAL to space -->prefixToInfix(stack)
Postfix to Infix Algorithm
Same as Prefix to Infix algorithm except,
1) Step 1 must be changed – The input string will be pushed into the stack
2) Also the two parenthesis{ “ ( ” , ” ) ” } will be swapped where mentioned.
3) The output string will be reversed.
as i think this post will be a valuable resource for any computer science student!
Posts
