Write a program that translates arithmetic expressions written used the standard
ID: 3931893 • Letter: W
Question
Write a program that translates arithmetic expressions written used the standard infix notation, into RPN (Reserve Polish Notation). Your program should use a Java class Stack. You can choose to implement the Stack either using an array or using a linked list. Test your program by using inputs of different lengths and with different types of nested parentheses.
Implement a Java class Queue using circular arrays. Test your implementation and make sure all the methods work. Then use your class Queue to implement Ceasar’s Cypher with a repeating key.
Explanation / Answer
Algorithm infix2postfix(infix exp<b></b>ression string, postfix exp<b></b>ression string)
{
char *i,*p;
i = first element in infix exp<b></b>ression
p = first element in postfix exp<b></b>ression
while i is not null
{
while i is a space or tab
{
increment i to next character in infix exp<b></b>ression;
}
if( i is an operand )
{
p = i;
increment i to next character in infix exp<b></b>ression;
increment p to next character in postfix exp<b></b>ression;
}
if( i is '(' )
{
stack_push(i);
increment i to next character in infix exp<b></b>ression;
}
if( i is ')' )
{
while( element at top of stack != '(' )
{
p = element at top of stack;
increment p to next character in postfix exp<b></b>ression;
}
increment i to next character in infix exp<b></b>ression;
}
if( i is an operator )
{
if( stack is empty )
stack_push(i);
else
{
while priority(element at top of stack) >= priority(i)
{
p = element at top of stack;
increment p to next character in postfix exp<b></b>ression;
}
stack_push(i);
}
increment i to next character in infix exp<b></b>ression;
}
}
while stack is not empty
{
p = stack_pop()
increment p to next character in postfix exp<b></b>ression;
}
p = '';
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.