Waliul

Prefix Expression Evaluation

Jan 15th, 2022
1,225
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define mx 30
  5. int i(0);
  6.  
  7. class node
  8. {
  9. public:
  10.     int info;
  11.     node *link;
  12. };
  13.  
  14. node *head = NULL, *tmp = NULL;
  15.  
  16. void push(int val)
  17. {
  18.     node *ptr = new node();
  19.     ptr->info = val;
  20.     ptr->link = head;
  21.     head = ptr;
  22.     i++;
  23. }
  24.  
  25. int top()
  26. {
  27.     return head->info;
  28. }
  29.  
  30. int pop()
  31. {
  32.     int val = head->info;
  33.     head = head->link;
  34.     return val;
  35. }
  36.  
  37. bool isEmpty()
  38. {
  39.     if(head == NULL)
  40.     {
  41.         cout<<"\nStack Underflow!!!!\n\n";
  42.         return true;
  43.     }
  44.     return false;
  45. }
  46.  
  47. bool isFull()
  48. {
  49.     if(i >= mx)
  50.     {
  51.         cout<<"\nStack Overflow!!!\n\n";
  52.         return true;
  53.     }
  54.     return false;
  55. }
  56.  
  57. bool isOperator(char ch)
  58. {
  59.     if(ch == '+' || ch == '-' || ch == '*' || ch == '/')
  60.         return true;
  61.     return false;
  62. }
  63.  
  64. bool isNumeric(char ch)
  65. {
  66.     if(ch >= '0' && ch <= '9')
  67.         return true;
  68.     return false;
  69. }
  70.  
  71. int perform(int a, int b, char ch)
  72. {
  73.     if(ch == '+')
  74.         return a+b;
  75.     if(ch == '-')
  76.         return a-b;
  77.     if(ch == '*')
  78.         return a*b;
  79.     if(ch == '/')
  80.         return a/b;
  81. }
  82.  
  83. int evaluatePrefix(string exp)
  84. {
  85.     int i, j, k, sz, op1, op2;
  86.     sz = exp.size() - 1;
  87.     for(i = sz; i >= 0; i--)
  88.     {
  89.         if(exp[i] == ' ' || exp[i] == ',')
  90.             continue;
  91.         else if(isOperator(exp[i]))
  92.         {
  93.             op1 = pop();
  94.             op2 = pop();
  95.             k = perform(op1, op2, exp[i]);
  96.             push(k);
  97.         }
  98.         else if(isNumeric(exp[i]))
  99.         {
  100.             int a, b, c, d, oprnd;
  101.             oprnd = 0;
  102.             d = 1;
  103.             for(; i >= 0 && isNumeric(exp[i]); i--, d *= 10)
  104.                 oprnd = (exp[i] - '0') * d + oprnd;
  105.             i++;
  106.             push(oprnd);
  107.         }
  108.         else
  109.         {
  110.             cout<<"The expression contains wrong symbol.\n";
  111.             exit(0);
  112.         }
  113.     }
  114.     return k;
  115. }
  116.  
  117. int main()
  118. {
  119.     int i, j, k, n;
  120.     string str;
  121.     getline(cin, str);
  122.     cout<<evaluatePrefix(str)<<endl;
  123. }
RAW Paste Data