Theory: • Algorithm of stack-based RPN (postfix) expression evaluation: Question
ID: 3621736 • Letter: T
Question
Theory:• Algorithm of stack-based RPN (postfix) expression evaluation:
Question: how do you check for invalid format of expression?
• Algorithm of stack-based PN (prefix) expression evaluation
Question: when to terminate?
• More on wikipedia on RPN/PN expressions:
http://en.wikipedia.org/wiki/Reverse_Polish_notation
http://en.wikipedia.org/wiki/Polish_notation
Check: are top 2 elements of the stack both numbers?
If yes:
pop from stack (number x)
pop from stack (number y)
pop from stack (op)
push the result of (y op x) on stack
go back to Check
If no:
push the next element of expression on stack
go back to Check
scan the expression from left to right
for each element, do the following:
{
if it is a number:
push the number on stack
if it is an operation:
pop from stack number x
pop from stack number y
push the result of (y op x) on stack
}
• Specification:
• Operations: you need to implement addition (+), subtraction (-),
multiplication (*), and division (/) for integer numbers.
• Numbers: single-digit or multiple-digit integer numbers (according to levels of
difficulty) in input expression.
• Input:
?? user will provide a character string of RPN or PN expression, valid or invalid,
with numbers and operations separated by space.
?? “q” to exit the program.
• Output:
?? “invalid expression” if input is not in valid RPN or PN form.
?? identify “RPN” or “PN” according to the input string (for level 1 it’s always RPN).
?? output the result of the expression on the same line.
• Difficulty levels & project group:
Level 1: single-digit RPN expression evaluation
Level 2: single-digit RPN & PN expression evaluation
Level 3: multi-digit RPN & PN expression evaluation
•• Extra credit will be given if the requirement above your required level is achieved.
• Your program should meet the exact specification and input / output format.
• Please make sure your stack can handle no less than 32 elements.
• Submission:
• Submit on blackboard before midnight of Nov 28th (Sunday of week 14):
?? your .s file (well commented).
?? a brief write-up on: 1) what features are implemented; 2) how is work divided if
you have multiple group members.
• Sign up for a 15 min demo / Q&A during the 15th week. (If you finish up early, we can
arrange some time during the 14th week as well.)
?? Sample input / output (red indicating input):
input expression: (q to quit)
- + 200 * 15 2 * 100 + 67 02
PN -900
input expression: (q to quit)
16 3 25 + 40 - *
RPN -192
input expression: (q to quit)
32 5 83 * + 42 * 6 + * 2
invalid format!
input expression: (q to quit)
- 3 2 * 5 22 + 4 / 64 2
invalid format!
for level 2
input expression: (q to quit)
18000 3 5 - /
RPN -9000
input expression: (q to quit)
q
bye!
input expression: (q to quit)
6 3 5 + 4 - *
RPN 24
input expression: (q to quit)
- + 2 * 5 2 * 4 + 6 2
invalid format!
input expression: (q to quit)
6
RPN 6
input expression: (q to quit)
3 5 8 * + 4 * 6 + * 2
invalid format!
input expression: (q to quit)
3 2 2 5 + - +
RPN -2
input expression: (q to quit)
q
bye!
level 3
input expression: (q to quit)
6 3 5 + 4 - *
RPN 24
input expression: (q to quit)
/ 7 2
PN 3
input expression: (q to quit)
- + 2 * 5 2 * 4 + 6 2
PN -20
input expression: (q to quit)
3 5 8 * + 4 * 6 + * 2
invalid format!
input expression: (q to quit)
- 3 2 * 5 2 * 4 + 6 2
invalid format!
input expression: (q to quit)
8 2 4 - /
RPN -4
input expression: (q to quit)
q
bye!
Explanation / Answer
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<conio.h>
#define N 80
typedef enum{FALSE,TRUE} bool;
#include "stack.h"
#include "queue.h"
#define NOPS 7
char operators []="()^/*+-";
int priorities[]={4,4,3,2,2,1,1}
char associates[]=" RLLLL";
char t[N];
char *tptr=t;
int getindex(char op)
{
int i;
for(i=0;i<NOPS;++)
if(operators[i]==op)
return i;
return -1;
}
int getpriority(char op)
{
return priorities[getIndex(op)];
}
char getAssociativity(char op)
{
return associates[getIndex(op)];
}
void process0p(char op,queue *q,stack *s)
{
switch(op)
{
case ')':
printf(" S pushing ) ");
sPush(s,op);
break;
case '(':
while(!qEmpty(q))
{
*tptr++ =qPop(q);
printf(" Q popping %c.... ",*(tptr-1));
}
while(!sEmpty(s))
{
char popop=sPop(s);
printf(" s popping %c.... ",popop);
if(popop==')')
break;
*tptr++=popop;
}
break;
default:
{
int priop;
char topop;
int pritop;
char asstop;
while(!sEmpty(s))
{
priop =getPriority(op);
topop =sTop(s);
pritop=getPriority(topop);
asstop=getAssociativity(topop);
if(pritop<priop||(pritop==priop && asstop=='L')||topop==')')
break;
while(!qEmpty(q))
{
*tptr++=qpop(q);
printf(" Q popping %c.... ", *(tptr-1));
}
*tptr++ =sPop(s);
printf(" S popping %c.... ", *(tptr-1));
}
printf(" S pushing %c... ", op);
sPush(s,op);
break;
}
}
}
bool isop(char op)
{
return (getIndex(op)!= .1);
}
char *in2pre(char *str )
{
char *sptr;
queue q={NULL};
stack s=NULL;
char *res=(char *)malloc(N*sizeof(char));
char *resptr =res;
tptr =t;
for(sptr=str+strlen(str)-1;sptr!=str-1;-sptr)
{
printf("processing %c tptr-t=%d.... ", *sptr,tptr-t);
if(isalpha(*sptr))
qPush(&q, *sptr);
else if(isop(*sptr))
process0p(*sptr,&q,&s);
else if(isspacce(*sptr))
;
else
{
fprintf(stderr,"ERROR:invalid char %c. ", *sptr);
return " ";
}
}
while(!qEmpty(&q))
{
*tptr++ =qPop(&q);
printf(" Q popping %c... ", *(tptr-1));
}
while(!sEmpty(&s))
{
*tptr++=sPop(&s);
printf(" S popping %c... ", *(tptr-1));
}
*tptr =0;
printf("t=%s ", t);
for(-tptr; tptr!=t-1; -tptr)
{
*resptr++=*tptr;
}
*resptr=0;
return res;
}
int main()
{
char s[N];
puts("enter infix freespaces max 80.");
gets(s);
while(*s)
{
puts(in2pre(s));
gets(s);
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.