ONP - Transform the Expression

See on SPOJ

Transform the algebraic expression with brackets into RPN form (Reverse Polish Notation). Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: a,b,...,z. Assume that there is only one RPN form (no expressions like a*b*c).  

In simple words, convert an infix expression to postfix.

Input

t [the number of expressions <= 100]
expression [length <= 400]
[other expressions]

Text grouped in [ ] does not appear in the input file.

 

Output

The expressions in RPN form, one per line.

 

Example

Input:
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

Output:
abc*+
ab+zx+*
at+bac++cd+^*

 Solution- Using Stack.

It uses a stack which is used to hold operators rather than numbers. The purpose of the stack is to reverse the order of the operators in the expression. It also serves as a storage structure, since no operator can be printed until both of its operands have appeared.

In this algorithm, all operands are printed (or sent to output) when they are read. There are more complicated rules to handle operators and parentheses.

Example 
A * (B + C) becomes A B C + *
A subexpression in parentheses must be done before the rest of the expression.

	current symbol	operator stack	postfix string
1	A		A
2	*	*	A
3	(	* (	A B
4	B	* (	A B
5	+	* ( +	A B
6	C	* ( +	A B C
7	)	*	A B C +
8			A B C + *

Since expressions in parentheses must be done first, everything on the stack is saved and the left parenthesis is pushed to provide a marker. When the next operator is read, the stack is treated as though it were empty and the new operator (here the '+' sign) is pushed on. Then when the right parenthesis is read, the stack is popped until the corresponding left parenthesis is found. Since postfix expressions have no parentheses, the parentheses are not printed.

Here is the code to implement this. Time taken 0.00 sec.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182

//infix to postfix //stack #include <bits/stdc++.h> #define max1(x,y) (x)>(y)?(x):(y) #define s(n) scanint(n) #define sc(n) scanf(" %c",&n) #define sl(n) scanf("%ld",&n) #define sll(n) scanf("%lld",&n) #define sf(n) scanf("%lf",&n) #define ss(n) scanf("%s",n) #define INF (int)1e9 #define EPS 1e-9 #define bitcount __builtin_popcount #define gcd __gcd #define forall(i,a,b) for(int i=a;i<b;i++) #define all(a) a.begin(), a.end() #define pb push_back #define sz(a) ((int)(a.size())) #define mp make_pair #define checkbit(n,b) ( (n >> b) & 1) #define gc getchar_unlocked #define l long using namespace std ; inline void scanint(int &x) { register int c = gc(); x = 0; int neg = 0; for(;((c<48 || c>57) && c != '-');c = gc()); if(c=='-') {neg=1;c=gc();} for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;} if(neg) x=-x; } // Function to convert Infix expression to postfix string InfixToPostfix(string expression); // Function to verify whether an operator has higher precedence over other int HasHigherPrecedence(char operator1, char operator2); // Function to verify whether a character is operator symbol or not. bool IsOperator(char C); // Function to verify whether a character is alphanumeric chanaracter (letter or numeric digit) or not. bool IsOperand(char C); int main() { string expression; int t; s(t); while(t--){ getline(cin,expression); string postfix = InfixToPostfix(expression); cout<<postfix<<"\n"; } } // Function to evaluate Postfix expression and return output string InfixToPostfix(string expression) { // Declaring a Stack from Standard template library in C++. stack<char> S; string postfix = ""; // Initialize postfix as empty string. for(int i = 0;i< expression.length();i++) { // Scanning each character from left. // If character is a delimitter, move on. if(expression[i] == ' ' || expression[i] == ',') continue; // If character is operator, pop two elements from stack, perform operation and push the result back. else if(IsOperator(expression[i])) { while(!S.empty() && S.top() != '(' && HasHigherPrecedence(S.top(),expression[i])) { postfix+= S.top(); S.pop(); } S.push(expression[i]); } // Else if character is an operand else if(IsOperand(expression[i])) { postfix +=expression[i]; } else if (expression[i] == '(') { S.push(expression[i]); } else if(expression[i] == ')') { while(!S.empty() && S.top() != '(') { postfix += S.top(); S.pop(); } S.pop(); } } while(!S.empty()) { postfix += S.top(); S.pop(); } return postfix; } // Function to verify whether a character is english letter or numeric digit. // We are assuming in this solution that operand will be a single character bool IsOperand(char C) { if(C >= '0' && C <= '9') return true; if(C >= 'a' && C <= 'z') return true; if(C >= 'A' && C <= 'Z') return true; return false; } // Function to verify whether a character is operator symbol or not. bool IsOperator(char C) { if(C == '+' || C == '-' || C == '*' || C == '/' || C== '^') return true; return false; } // Function to verify whether an operator is right associative or not. int IsRightAssociative(char op) { if(op == '^') return true; return false; } // Function to get weight of an operator. An operator with higher weight will have higher precedence. int GetOperatorWeight(char op) { int weight = -1; switch(op) { case '+': case '-': weight = 1; case '*': case '/': weight = 2; case '^': weight = 3; } return weight; } // Function to perform an operation and return output. int HasHigherPrecedence(char op1, char op2) { int op1Weight = GetOperatorWeight(op1); int op2Weight = GetOperatorWeight(op2); // If operators have equal precedence, return true if they are left associative. // return false, if right associative. // if operator is left-associative, left one should be given priority. if(op1Weight == op2Weight) { if(IsRightAssociative(op1)) return false; else return true; } return op1Weight > op2Weight ? true: false; }

If there is another solution (without stack) please let us know. You will be given credit.