fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define MAX_SIZE 50
  3. using namespace std;
  4.  
  5. struct Node{
  6. 	char data;
  7. 	struct Node *left;
  8. 	struct Node *right;
  9. };
  10.  
  11. class InfixToPrePost{
  12. public:
  13.     /** Initialize your data structure here. */
  14.     char a[MAX_SIZE];
  15. 	int top;
  16.  
  17.     InfixToPrePost() {
  18.         top = -1;
  19.     }
  20.  
  21. 	void push(char c){
  22. 		if(top == MAX_SIZE - 1){
  23. 			cout<<"Stack is full\n";
  24. 			return;
  25. 		}
  26.  
  27. 		a[++top] = c;
  28. 	}
  29.  
  30. 	char topElement(){
  31. 		return a[top];
  32. 	}
  33.  
  34. 	char pop(){
  35. 		return a[top--];
  36. 	}
  37.  
  38. 	bool isEmpty(){
  39. 		return top == -1;
  40. 	}
  41.  
  42. 	int priority(char c){
  43. 		if(c == '(')
  44. 			return 0;
  45.  
  46. 		if(c == '+' || c== '-')
  47. 			return 1;
  48.  
  49. 		if(c == '*' || c == '/' || c == '%')
  50. 			return 2;
  51.  
  52. 		if(c == '^')
  53. 			return 3;
  54.  
  55. 		return 0;
  56. 	}
  57.  
  58. 	string convertToPostfix(string inp){
  59. 		string ans = "";
  60.  
  61. 		for(int i = 0; i < inp.length(); ++i){
  62.  
  63. 			if(isalnum(inp[i])){
  64. 				ans += inp[i];
  65. 			}
  66. 			else if(inp[i] == '('){
  67. 				push('(');
  68. 			}
  69. 			else if(inp[i] == ')'){
  70. 				char t;
  71.  
  72. 				while((t = pop()) != '(')
  73. 					ans += t;
  74. 			}
  75. 			else{
  76. 				while(!isEmpty() && priority(topElement()) >= priority(inp[i])){
  77. 					ans += pop();
  78. 				}
  79.  
  80. 				push(inp[i]);
  81. 			}
  82. 		}
  83.  
  84. 		while(!isEmpty()){
  85. 			ans += pop();
  86. 		}
  87.  
  88. 		return ans;
  89. 	}
  90.  
  91. 	string convertToPrefix(string inp){
  92.  
  93. 		int len = inp.length();
  94.  
  95. 		for(int i = 0; i < len/2 + 1; ++i){
  96. 			char t = (inp[i] == '(' ? ')' : (inp[i] == ')' ? '(': inp[i]));
  97. 			inp[i] = (inp[len-i-1] == '(' ? ')' : (inp[len-i-1]  == ')' ? '(': inp[len-i-1]));
  98. 			inp[len-i-1] = t;
  99. 		}
  100.  
  101. 		inp = convertToPostfix(inp);
  102.  
  103. 		reverse(inp.begin(), inp.end());
  104.  
  105. 		return inp;
  106. 	}
  107. };
  108.  
  109. class ExpressionTree{
  110. 	public:
  111. 	struct Node *root;
  112. 	stack<Node*> st;
  113.  
  114. 	ExpressionTree(){
  115. 		root = NULL;
  116. 	}
  117.  
  118. 	Node *getNode(char val){
  119. 		Node *newNode = new Node;
  120.  
  121. 		newNode->data = val;
  122. 		newNode->left = newNode->right = NULL;
  123.  
  124. 		return newNode;
  125. 	}
  126.  
  127. 	void convertInfixToTree(string str){
  128. 		InfixToPrePost obj;
  129.  
  130. 		str = obj.convertToPostfix(str);
  131.  
  132. 		convertPostfixToTree(str);
  133. 	}
  134.  
  135. 	void convertPostfixToTree(string &str){
  136.  
  137. 		for(auto &val: str){
  138.  
  139. 			if(isalnum(val)){
  140. 				st.push(getNode(val));
  141. 			}
  142. 			else{
  143. 				Node *newNode = getNode(val);
  144. 				newNode->right = st.top(); st.pop();
  145. 				newNode->left = st.top(); st.pop();
  146. 				st.push(newNode);
  147. 			}
  148. 		}
  149.  
  150. 		root = st.top(); st.pop();
  151. 	}
  152.  
  153. 	void convertPrefixToTree(string &str){
  154.  
  155. 		for(int i = str.size()-1; i > -1; --i){
  156.  
  157. 			if(isalnum(str[i])){
  158. 				st.push(getNode(str[i]));
  159. 			}
  160. 			else{
  161. 				Node *newNode = getNode(str[i]);
  162. 				newNode->left = st.top(); st.pop();
  163. 				newNode->right = st.top(); st.pop();
  164. 				st.push(newNode);
  165. 			}
  166. 		}
  167.  
  168. 		root = st.top(); st.pop();
  169. 	}
  170.  
  171. 	int evaluateExpression(Node *rt){
  172. 		if(!rt->left && !rt->right)
  173. 			return rt->data - '0';
  174.  
  175. 		int left = evaluateExpression(rt->left);
  176. 		int right = evaluateExpression(rt->right);
  177.  
  178. 		return op(rt->data, left, right);
  179. 	}
  180.  
  181. 	int op(char &op, int &left, int &right){
  182. 		if(op == '+')
  183. 			return left + right;
  184. 		else if(op == '*')
  185. 			return left * right;
  186. 		else if(op == '-')
  187. 			return left - right;
  188. 		else if(op == '%')
  189. 			return left % right;
  190. 		else if(op == '/')
  191. 			return left / right;
  192. 	} 
  193.  
  194. 	void inOrder(Node *rt){
  195. 		if(!rt)
  196. 			return;
  197.  
  198. 		inOrder(rt->left);
  199. 		cout<<rt->data<<" ";
  200. 		inOrder(rt->right);
  201. 	}
  202.  
  203. 	void postOrder(Node *rt){
  204. 		if(!rt)
  205. 			return;
  206.  
  207. 		postOrder(rt->left);
  208. 		postOrder(rt->right);
  209. 		cout<<rt->data<<" ";
  210. 	}
  211.  
  212. 	void preOrder(Node *rt){
  213. 		if(!rt)
  214. 			return;
  215.  
  216. 		cout<<rt->data<<" ";
  217. 		preOrder(rt->left);
  218. 		preOrder(rt->right);
  219. 	}
  220. };
  221.  
  222. int main(){
  223. 	ios::sync_with_stdio(0);
  224. 	cin.tie(0);
  225. 	cout.tie(0);
  226.  
  227. 	int opt;
  228. 	string expression;
  229.  
  230. 	ExpressionTree etree;
  231.  
  232. 	cout<<"Operations available on Expresssion tree are:\n";
  233. 	cout<<"1. Infix to expression tree\n2. Postfix to expression tree\n3. Prefix to expression tree\n"
  234. 	"4. InOrder\n5. PreOrder\n6. PostOrder\n7. Evaluate expression\n8. Exit\n";
  235. 	cout<<"*****************************************************************\n";
  236. 	while(true){
  237. 		cin>>opt;
  238. 		switch(opt){
  239. 			case 1:
  240. 				cin>>expression;
  241. 				cout<<"Converting the infix expression \""
  242. 				<<expression<<"\" to expression tree.\n";
  243. 				etree.convertInfixToTree(expression);
  244. 				break;
  245. 			case 2:
  246. 				cin>>expression;
  247. 				cout<<"Converting the postfix expression \""
  248. 				<<expression<<"\" to expression tree.\n";
  249. 				etree.convertPostfixToTree(expression);
  250. 				break;
  251. 			case 3:
  252. 				cin>>expression;
  253. 				cout<<"Converting the prefix expression \""
  254. 				<<expression<<"\" to expression tree.\n";
  255. 				etree.convertPrefixToTree(expression);
  256. 				break;
  257. 			case 4:
  258. 				cout<<"InOrder traversal: ";
  259. 				etree.inOrder(etree.root); cout<<"\n";
  260. 				break;
  261. 			case 5:
  262. 				cout<<"PreOrder traversal: ";
  263. 				etree.preOrder(etree.root); cout<<"\n";
  264. 				break;
  265. 			case 6:
  266. 				cout<<"PostOrder traversal: ";
  267. 				etree.postOrder(etree.root); cout<<"\n";
  268. 				break;
  269. 			case 7:
  270. 				cout<<"The evaluation result of \""<<expression<<"\" is: "
  271. 				<<etree.evaluateExpression(etree.root)<<"\n";
  272. 				break;
  273. 			case 8:
  274. 				exit(0);
  275. 		}
  276. 		cout<<"*****************************************************************\n";
  277. 	}
  278.  
  279. 	return 0;
  280. }
Success #stdin #stdout 0s 4492KB
comments (?)
stdin
copy 
1
2*3+5-8/2
4 5 6 7
2
23*582/-+
4 5 6 7
3
+*23-5/82
4 5 6 7 8
stdout
copy 
Operations available on Expresssion tree are:
1. Infix to expression tree
2. Postfix to expression tree
3. Prefix to expression tree
4. InOrder
5. PreOrder
6. PostOrder
7. Evaluate expression
8. Exit
*****************************************************************
Converting the infix expression "2*3+5-8/2" to expression tree.
*****************************************************************
InOrder traversal: 2 * 3 + 5 - 8 / 2 
*****************************************************************
PreOrder traversal: - + * 2 3 5 / 8 2 
*****************************************************************
PostOrder traversal: 2 3 * 5 + 8 2 / - 
*****************************************************************
The evaluation result of "2*3+5-8/2" is: 7
*****************************************************************
Converting the postfix expression "23*582/-+" to expression tree.
*****************************************************************
InOrder traversal: 2 * 3 + 5 - 8 / 2 
*****************************************************************
PreOrder traversal: + * 2 3 - 5 / 8 2 
*****************************************************************
PostOrder traversal: 2 3 * 5 8 2 / - + 
*****************************************************************
The evaluation result of "23*582/-+" is: 7
*****************************************************************
Converting the prefix expression "+*23-5/82" to expression tree.
*****************************************************************
InOrder traversal: 2 * 3 + 5 - 8 / 2 
*****************************************************************
PreOrder traversal: + * 2 3 - 5 / 8 2 
*****************************************************************
PostOrder traversal: 2 3 * 5 8 2 / - + 
*****************************************************************
The evaluation result of "+*23-5/82" is: 7
*****************************************************************
https://ideone.com/45LIh1
Infix, Prefix, Postfix to expression tree
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!