In C++: Task: Evaluate a postfix expression using a stack. See Problem #12, pg.
ID: 3890822 • Letter: I
Question
In C++:
Task: Evaluate a postfix expression using a stack. See Problem #12, pg. 387, in the Nyhoff textbook.
Input: The user will provide a postfix expression consisting of single-digit whole numbers and single-char operators (+, -, *, and /). The input should be accepted as a string.
Processing: Use a linked list stack implementation for the program. Only numbers will be stored in the stack. When a digit is read from the input string, it will be pushed onto the stack. When an operator is read from the string, two numbers will be popped from the stack and the operator will be used to evaluate them; then the result will be pushed back onto the stack.
Assume that only valid postfix expressions will be entered, so extensive data validation is not needed. Calculations will be done on the numbers as integers. Permit the user to enter multiple expressions for evaluation.
Output: As specified by Problem #12, pg. 387.
Sample expressions:
infix: postfix: result:
(2 + 7 ) * (3 - 6) 2 7 + 3 6 - * -27
3 - 4 - 1 + (5 / 2) 3 4 - 1 - 5 2 / + 0
Explanation / Answer
A. Background of the Postfix expression and little explanation:
* example from above- 2 7+3 6 - *
- dividing the above expression into chunks- [2] [7] [+] [3] [6] [-] [*]
Now, widely speaking the differentiating pattern from the above expression is presence of numbers (27 and 36) values and mathematical operators (+, add etc.).
POSTFIX fundamental-
Algorithm-
2. Scan [+], pop two numbers(operands) [2] and [7] and apply the operator [2] + [7] the result is 9, as it is number so push back to stack. STACK- 9
3. Scan [3] and [6], as they are number so push to the stack and move on. STACK- 6 | 3 | 9
4. Scan [-], pop two numbers [6] and [3] and apply the operator [3] – [6] the result is -3, push back to stack and move on. STACK - -3 | 9
5. Scan [*], is operator so pop two numbers and apply operator [9] – [-3] the result is -27
B. Program in C++
/*--- C++ Program to evaluate an Postfix expression using stacks (linked list implementation)--- */
#include <iostream>
#include <conio.h>
#include <string.h>
using namespace std;
//New Linked List entity(synonymous to class)
struct ListNode
{
int data;
ListNode *next;
}*node = NULL, *top = NULL, *save = NULL, *ptr;
//Pushing data into the stack
void push(int x)
{
node = new ListNode;
node->data = x;
node->next = NULL;
if (top == NULL)
top = node;
else
{
//adding the new node to the linked list
save = top;
top = node;
node->next = save;
}
}
//
char pop()
{
if (top == NULL)
{
cout<<"Stack Empty!";
}
else
{
ptr = top;
top = top->next;
return(ptr->data);
}
}
int main()
{
//stores the expression provided by the user
char x[30];
int a, b;
cout<<"enter the postfix expression ";
cin>>x;
for (int i = 0; i < strlen(x); i++)
{
//ASCII values 48 to 57 translates to 0-9
if (x[i] >= 48 && x[i] <= 57){
push(x[i]-'0');
}
//Ascci values 42 to 47 translates to general maths operator *,+,',',-,.,/
//out of which we will be handling +,-,* and /
else if (x[i] >= 42 && x[i] <= 47)
{
a=pop();
b=pop();
switch(x[i])
{
case '+':
push(a+b);
break;
case '-':
push(a-b);
break;
case '*':
push(a*b);
break;
case '/':
push(a/b);
break;
}
}
}
char d=pop();
cout<<"Result is "<<d<<endl;
getch();
}