Advanced Search

Infix notation to Reverse Polish Notation

/ Published in: C++
Save to your folder(s)
The bugged version: Somehow, it prints random characters to me like [] except the spaces filled in and other accented letters when I input more parenthesis and longer input.

How to use: example->
input:
3
1+2
(1+2)*(6-2)
6-7*(9*10)/8

output:
1 2 +
1 2 + 6 2 - *
6 7 - 9 10 ** 8 /

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  1. #include <iostream>
  2. #include <cctype>
  3. #include <string>
  4. #include <list>
  5. #include <stack>
  6.  
  7. using namespace std;
  8.  
  9. char pop(list<char> & a)                 //Pops the stack and returns it, I use it to append to output vector
  10. {
  11.     char result = a.front();
  12.     a.pop_front();
  13.     return result;
  14. }
  15.  
  16.  
  17. int main()
  18. {
  19.     int num;
  20.     string in;
  21.     cin >> num;
  22.  
  23.     string out;                                              //stores outputed characters front operator stack
  24.     list<char> opr;
  25.     for(int zed=0; zed<num; zed++) {
  26.     cin >> in;
  27.  
  28.     for(int i =0; i < in.length(); i++)
  29.     {
  30.         switch(in[i])                                         //Gets operator gets their precedence and pushes them into the stack(list) and
  31.                                                               //output string
  32.         {
  33.             case '(': opr.push_front(in[i]);
  34.                       break;
  35.             case ')':  while(opr.front()!='(' && !opr.empty())
  36.                        {
  37.                           out.push_back(pop(opr));
  38.                        }
  39.  
  40.                       opr.pop_front();
  41.                       break;
  42.             case '-': if(opr.front() == '+' || '*' || '^' || '/' || '%')
  43.                       {
  44.                           out.push_back(pop(opr));
  45.                           opr.push_front(in[i]);
  46.                       }
  47.                       else opr.push_front(in[i]);
  48.                       out.push_back(' ');
  49.                       break;
  50.             case '+': if(opr.front() == '-' || '*' || '^' || '/' || '%')
  51.                       {
  52.                           out.push_back(pop(opr));
  53.                           opr.push_front(in[i]);
  54.                       }
  55.                       else opr.push_front(in[i]);
  56.                       out.push_back(' ');
  57.                       break;
  58.             case '*': if(opr.front() == '^' || '/' || '%')
  59.                       {
  60.                           out.push_back(pop(opr));
  61.                           opr.push_front(in[i]);
  62.                       }
  63.                       else opr.push_front(in[i]);
  64.                       out.push_back(' ');
  65.                       break;
  66.             case '^': opr.push_front(in[i]);
  67.                       out.push_back(' ');
  68.                       break;
  69.             case '/': if(opr.front() == '^' || '*' || '%')
  70.                       {
  71.                           out.push_back(pop(opr));
  72.                           opr.push_front(in[i]);
  73.                       }
  74.                       else opr.push_front(in[i]);
  75.                       out.push_back(' ');
  76.                       break;
  77.             default: if(isdigit(in[i]) || isalpha(in[i]))   //Default: if character is a digit or a letter append it to output
  78.                 out.push_back(in[i]);
  79.         }
  80.  
  81.     }
  82.  
  83.     while(!opr.empty())                     //if the stack isn't empty push the rest into the output vector
  84.         {
  85.             out.push_back(pop(opr));
  86.             opr.pop_front();
  87.         }
  88.  
  89.     out.erase(remove(out.begin(), out.end(),'('), out.end());  //remove those stupid parenthesis
  90.     out.push_back('\n');
  91. }
  92.  
  93. cout << out;
  94.  
  95.     return 0;
  96. }

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.