We normally write arithmetical expressions using infix notation, meaning that th

Question

We normally write arithmetical expressions using infix notation, meaning that the operator appears between its two operands, as in "4 + 5". In postfix notation, the operator appears after its operands, as in "4.3 5.0 +". Here is a slightly more complex postfix expression: "25 12 7 - 2 * /". The equivalent infix expression is: "25 / ((12 - 7) * 2)". The result of that expression should be 2.5 (beware integer division). Postfix expressions don't require parentheses.

Write a function named postfixEval that uses a stack<double> (from the Standard Template Library) to evaluate postfix expressions. It should take a C-style string parameter that represents a postfix expression. The only symbols in the string will be +, -, *, /, digits and spaces. '+' and '-' will only appear in the expression string as binary operators - not as unary operators that indicate the sign of a number. The return type should be double. You may find the isdigit() function useful in parsing the expression. You may also use strtok() and atof().

Hint: Read a postfix expression from left to right. When you read a number, push it on the stack. When you read an operand, pop the top two numbers off the stack, apply the operator to them, and push the result on top of the stack. At the end, the result of the expression should be the only number on the stack.

File must be called: postfixEval.cpp

Explanation / Answer

#include <stdio.h>
#include <math.h>
#define MAX 50
void push(char[],char);
void in_push(double[], double);
int pop();
int prec(char);
double eval(char[],int,double[]);
int top = 0;
void main() {
double eval_stack[MAX];
int op_count=0;
char stack[MAX], exps[MAX], symbols[MAX];
int i=0,j=0,len,check;
while((symbols[i]=getchar())!=' ') {
if(symbols[i]!=' ' || symbols[i]!=' ') {
if(symbols[i]=='+' || symbols[i]=='-' || symbols[i]=='/' || symbols[i]=='*' || symbols[i]=='^')
op_count++;
i++;
}
}
symbols[i]='#';
symbols[++i]='';
len = strlen(symbols);
stack[top] = '#';
for(i=0; i<=len; i++)
{
if(symbols[i]>='a' && symbols[i]<='z')
{
exps[j]=symbols[i];
j++;
}
switch(symbols[i])
{
case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':
//if(symbols[i]>='a' && symbols[i]<='z')
{
exps[j]=symbols[i];
j++;
break;
case '+': case '-': case '*': case '/': case '^':
exps[j++] = ' ';
while(prec(symbols[i]) <= prec(stack[top]))
{
exps[j] = stack[top];
pop();
//printf(" %d %d ", top,j);
j++;
}
if(prec(symbols[i]) > prec(stack[top]))
{
push(stack,symbols[i]);
}
break;
case '(':
push(stack,symbols[i]);
break;
case ')':
while(stack[top]!='(')
{
exps[j] = stack[top];
pop();
j++;
}
pop();
break;
case '#':
exps[j++] = ' ';
while(stack[top]!='#')
{
exps[j] = stack[top];
pop();
j++;
}
pop();
break;
}
}
exps[j]='';
printf("Postfix: %s", exps);
for(i=0; i<j; i++)
if(exps[i]=='a')
check = 1;
if(check!=1)
printf(" Solution: %.1f", eval(exps,j,eval_stack));
}
double eval(char exps[],int exps_len,double eval_stack[])
{
int i; int len=exps_len,temp;
double in_temp[MAX],t;
int count,power,j,in_count;
count=power=j=t=in_count=0;
double result;
for(i=0; i<len; i++)
{
switch(exps[i])
{
case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':
in_temp[i] = exps[i]-'0';
j=i+1;
while(exps[j]>='0' && exps[j]<='9')
{
in_temp[j] = exps[j]-'0';
j++;
}
count = i;
while(in_temp[count]<='0' && in_temp[count]<='9')
{
power = (j-count)-1;
t = t + in_temp[count]*(pow(10,power));
power--;
count++;
}
in_push(eval_stack,t);
i=j-1;
t=0;
break;
case '+':
temp = pop();
pop();
result = eval_stack[temp] + eval_stack[temp+1];
in_push(eval_stack,result);
break;
case '-':
temp = pop();
pop();
result = eval_stack[temp] - eval_stack[temp+1];
in_push(eval_stack,result);
break;
case '*':
temp = pop();
pop();
result = eval_stack[temp] * eval_stack[temp+1];
in_push(eval_stack,result);
break;
case '/':
temp = pop();
pop();
result = eval_stack[temp] / eval_stack[temp+1];
in_push(eval_stack,result);
break;
case '^':
temp = pop();
pop();
result = pow(eval_stack[temp],eval_stack[temp+1]);
in_push(eval_stack,result);
break;
}
}
return eval_stack[top];
}
int prec(char a)
{
if(a=='^')
return 3;
else if(a=='*' || a=='/' || a=='%')
return 2;
else if(a=='+' || a=='-')
return 1;
else if(a=='(')
return 0;
else
return -1;
}
void push(char stack[], char ele)
{
if(top>=MAX)
{
printf(" Stack Overflow");
exit(1);
}
stack[++top] = ele;
}
void in_push(double stack[], double ele)
{
if(top>=MAX)
{
printf(" Stack Overflow");
exit(1);
}
stack[++top] = ele;
}
int pop()
{
if(top<0)
{
printf(" Stack Underflow");
exit(1);
}
top = top - 1;
return top;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.