0

how can i use reverse polish notation in link list using stack i need to reverse the numbers>_<

#include<stdio.h>
#include<stdlib.h>
#define p printf
#define s scanf
struct node
{
       int data;
       struct node *link;
};typedef struct node *nodepointer;
void push(nodepointer &top,int num)
{
     nodepointer newnode;
     newnode=(nodepointer)malloc(sizeof(struct node));
     newnode->data=num;
     newnode->link=top;
     top=newnode;
}
void display(nodepointer top)
{
if(top==NULL)
{
p("\nNothing to display");
}
else if(top!=NULL)
{
while(top->link!=NULL)
{
p("\n%i",top->data);
top=top->link;
}
p("\n%i",top->data);
}
}
void pop_add(nodepointer top)
{
     nodepointer after;
     nodepointer before;
     if(top==NULL || top->link==NULL)
     p("\nList is empty or must have two operands first before inserting operator...");
     else
     {
         before=NULL;
         after=top;
         while(after->link!=NULL)
         {
         before=after;
         after=after->link;
         }
         before->data=before->data+after->data;
         before->link=NULL;
         free(after);
         }   
}
void pop_mul(nodepointer top)
{
     nodepointer after;
     nodepointer before;
     if(top==NULL || top->link==NULL)
     p("\nList is empty or must have two operands first before inserting operator...");
     else
     {
         before=NULL;
         after=top;
         while(after->link!=NULL)
         {
         before=after;
         after=after->link;
         }
         before->data=before->data*after->data;
         before->link=NULL;
         free(after);
         }   
}
void pop_div(nodepointer top)
{
     nodepointer after;
     nodepointer before;
     if(top==NULL || top->link==NULL)
     p("\nList is empty or must have two operands first before inserting operator...");
     else
     {
         before=NULL;
         after=top;
         while(after->link!=NULL)
         {
         before=after;
         after=after->link;
         }
         before->data=before->data/after->data;
         before->link=NULL;
         free(after);
         }   
}
void pop_sub(nodepointer top)
{
     nodepointer after;
     nodepointer before;
     if(top==NULL || top->link==NULL)
     p("\nList is empty or must have two operands first before inserting operator...");
     else
     {
         before=NULL;
         after=top;
         while(after->link!=NULL)
         {
         before=after;
         after=after->link;
         }
         before->data=before->data-after->data;
         before->link=NULL;
         free(after);
         }   
}
main()
{
      nodepointer top;
      top=NULL;
      int number;
      int choice;
      char operators;
      do
      {
          p("\n[1].Push");
          p("\n[2].Display");
          p("\n[3].Add operator");
          p("\n[4].Reverse");
          p("\nKey choice: ");
          s("%i",&choice);
          switch(choice)
          {
      case 1:
           p("\nEnter number: ");
           s("%i",&number);
           push(top,number);
           break;
      case 2:
           display(top);
           break;
      case 3:
            p("\n[+].Addition");
            p("\n[-].Subtraction");
            p("\n[*].Multiplication");
            p("\n[/].Division");
            p("\nAdd operator");
            fflush(stdin);
            s("%c",&operators);
            if(operators=='+')
            {
            pop_add(top);
            break;
            }
            if(operators=='*')
            {
            pop_mul(top);
            break;
            }
            else if(operators=='-')
            {
            pop_sub(top);
            break;
            }
            else if(operators=='/')
            {
            pop_div(top);
            break;
      case 4:
            reverse(top);
            break;
            }
           }
           }while(1==1);
           system("pause");
           }

Edited by Dani: Formatting fixed

2
Contributors
1
Reply
3
Views
5 Years
Discussion Span
Last Post by BobS0327
0

First of all, the Reverse function is missing in your code. Secondly, you don't need a Reverse function in RPN. The "reverse" in Reverse Polish Notation means that the expression is reversed. For example a normal expression would be 3+4, In RPN the expression would be 3 4 +.

You won't be doing any type of "reversing" in a stack based implementation of RPN

You would need the following...

The stack itself:

#define STACK_SIZE 50
float stack[STACK_SIZE];
float *sp = stack-1;

And four functions. One function to push the variable on the stack, one to pop the variable from the stack, another function to apply the operator to the variables and finally a function parse the tokens.

Use the pointer to push and pop variables on and off the stack.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.