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 /


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.