fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #define MAX_SIZE 50
  4. using namespace std;
  5.  
  6. class InfixToPrePost{
  7. public:
  8.     /** Initialize your data structure here. */
  9.     char a[MAX_SIZE];
  10. 	int top;
  11.  
  12.     InfixToPrePost() {
  13.         top = -1;
  14.     }
  15.  
  16. 	void push(char c){
  17. 		if(top == MAX_SIZE - 1){
  18. 			cout<<"Stack is full\n";
  19. 			return;
  20. 		}
  21.  
  22. 		a[++top] = c;
  23. 	}
  24.  
  25. 	char topElement(){
  26. 		return a[top];
  27. 	}
  28.  
  29. 	char pop(){
  30. 		return a[top--];
  31. 	}
  32.  
  33. 	bool isEmpty(){
  34. 		return top == -1;
  35. 	}
  36.  
  37. 	int priority(char c){
  38. 		if(c == '(')
  39. 			return 0;
  40.  
  41. 		if(c == '+' || c== '-')
  42. 			return 1;
  43.  
  44. 		if(c == '*' || c == '/' || c == '%')
  45. 			return 2;
  46.  
  47. 		if(c == '^')
  48. 			return 3;
  49.  
  50. 		return 0;
  51. 	}
  52.  
  53. 	string convertToPostfix(string inp){
  54. 		string ans = "";
  55.  
  56. 		for(int i = 0; i < inp.length(); ++i){
  57.  
  58. 			if(isalnum(inp[i])){
  59. 				ans += inp[i];
  60. 			}
  61. 			else if(inp[i] == '('){
  62. 				push('(');
  63. 			}
  64. 			else if(inp[i] == ')'){
  65. 				char t;
  66.  
  67. 				while((t = pop()) != '(')
  68. 					ans += t;
  69. 			}
  70. 			else{
  71. 				while(!isEmpty() && priority(topElement()) >= priority(inp[i])){
  72. 					ans += pop();
  73. 				}
  74.  
  75. 				push(inp[i]);
  76. 			}
  77. 		}
  78.  
  79. 		while(!isEmpty()){
  80. 			ans += pop();
  81. 		}
  82.  
  83. 		return ans;
  84. 	}
  85.  
  86. 	string convertToPrefix(string inp){
  87.  
  88. 		int len = inp.length();
  89.  
  90. 		for(int i = 0; i < len/2 + 1; ++i){
  91. 			char t = (inp[i] == '(' ? ')' : (inp[i] == ')' ? '(': inp[i]));
  92. 			inp[i] = (inp[len-i-1] == '(' ? ')' : (inp[len-i-1]  == ')' ? '(': inp[len-i-1]));
  93. 			inp[len-i-1] = t;
  94. 		}
  95.  
  96. 		// cout<<inp<<"\n";
  97.  
  98. 		inp = convertToPostfix(inp);
  99.  
  100. 		reverse(inp.begin(), inp.end());
  101.  
  102. 		return inp;
  103. 	}
  104. };
  105.  
  106.  
  107. int main() {
  108. // 	ios::sync_with_stdio(0);
  109. // 	cin.tie(0);
  110.  
  111. 	string inp;
  112.  
  113. 	cin>>inp;
  114.  
  115. 	InfixToPrePost obj;
  116.  
  117. 	cout<<"Postfix: "<<obj.convertToPostfix(inp)<<"\n";
  118.  
  119. 	cout<<"Prefix: "<<obj.convertToPrefix(inp)<<"\n";
  120.  
  121. 	return 0;
  122. }
Success #stdin #stdout 0s 4548KB
comments (?)
stdin
copy 
(2*3+4*(8-6)/2)
stdout
copy 
Postfix: 23*486-*2/+
Prefix: +*23*4/-862
https://ideone.com/mtwH5r
Infix to postfix, prefix expression
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!