SHARE
TWEET

Untitled

a guest Apr 19th, 2019 94 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include "string"
  3. #include "conio.h"
  4. #include <cstdlib>
  5. #include <algorithm>
  6. #include <bits/stdc++.h>
  7. #include <stdio.h>
  8. #include <stdlib.h>
  9.  
  10. using namespace std;
  11.  
  12. template <class T>
  13. struct Node {
  14.       T data;
  15.       Node  *next;
  16.       Node(){
  17.        next=NULL;
  18.       }
  19.       Node(T x){
  20.        data=x;
  21.        next=NULL;
  22.       }
  23. };
  24. template <class T>
  25.     class Stack{
  26.       Node<T> *top=NULL;
  27.       public:
  28.       bool IsEmpty(){
  29.         if(top==NULL)
  30.             return true;
  31.         else
  32.             return false;
  33.       }
  34.       void Push(T x){
  35.         Node<T> *n=NULL;
  36.         n=new Node<T>(x);
  37.         //n->data=x;
  38.         if(IsEmpty())
  39.             top=n;
  40.         else{
  41.             n->next=top;
  42.             top=n;
  43.         }
  44.        }
  45.       T Pop(){
  46.        if(IsEmpty()==false){
  47.         Node<T> *t=top;
  48.         T x=top->data;
  49.         top=top->next;
  50.         t->next=NULL;
  51.         delete t;
  52.         return x;
  53.          }
  54.         }
  55.       void display(){
  56.        if(IsEmpty()==false){
  57.         Node<T> *t=top;
  58.         while(t->next!=NULL){
  59.             cout<<t->data<<endl;
  60.             t=t->next;
  61.             }
  62.           }
  63.         }
  64.       T Top(){
  65.           if(!IsEmpty())
  66.             return top->data;
  67.           else
  68.             exit(EXIT_FAILURE);
  69.  
  70.       }
  71.       void Clear(){
  72.         top=NULL;
  73.       }
  74.      };
  75.  
  76. //Function to return precedence of operators
  77. int prec(char c)
  78. {
  79.     if(c == '*' || c == '/')
  80.     return 2;
  81.     else if(c == '+' || c == '-')
  82.     return 1;
  83.     else
  84.     return -1;
  85. }
  86.  
  87. // The main function to convert infix expression
  88. //to postfix expression
  89. void infixToPostfix(string s)
  90. {
  91.     Stack<char> st;
  92.     st.Push('N');
  93.     int l = s.length();
  94.     string ns="";
  95.     for(int i = 0; i < l; i++)
  96.     {
  97.         // If the scanned character is an operand, add it to output string.
  98.         if((s[i] >= 'a' && s[i] <= 'z')||(s[i] >= 'A' && s[i] <= 'Z') || isdigit(s[i]))
  99.         ns+=s[i];
  100.  
  101.         // If the scanned character is an ‘(‘, push it to the stack.
  102.         else if(s[i] == '(')
  103.  
  104.         st.Push('(');
  105.  
  106.         // If the scanned character is an ‘)’, pop and to output string from the stack
  107.         // until an ‘(‘ is encountered.
  108.         else if(s[i] == ')')
  109.         {
  110.             while(st.Top() != 'N' && st.Top() != '(')
  111.             {
  112.                 char c = st.Top();
  113.                 st.Pop();
  114.             ns += c;
  115.             }
  116.             if(st.Top() == '(')
  117.             {
  118.                 //char c = st.Top();
  119.                 st.Pop();
  120.             }
  121.         }
  122.  
  123.         //If an operator is scanned
  124.         else{
  125.             while(st.Top() != 'N' && prec(s[i]) <= prec(st.Top()))
  126.             {
  127.                 char c = st.Top();
  128.                 st.Pop();
  129.                 ns += c;
  130.             }
  131.             st.Push(s[i]);
  132.         }
  133.  
  134.     }
  135.     //Pop all the remaining elements from the stack
  136.     while(st.Top() != 'N')
  137.     {
  138.         char c = st.Top();
  139.         st.Pop();
  140.         ns += c;
  141.     }
  142.  
  143.     cout << ns << endl;
  144.  
  145. }
  146.  
  147. //Driver program to test above functions
  148. int main()
  149. {
  150.     string exp = "(6+9)/3";
  151.     infixToPostfix(exp);
  152.     return 0;
  153. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top