Transform The Expression | CodeChef Solution

Hello coders, today we are going to solve Transform the Expression CodeChef Solution whose Problem Code is ONP.

Task

Reverse Polish Notation (RPN) is a mathematical notation where every operator follows all of its operands. For instance, to add three and four, one would write “3 4 +” rather than “3 + 4”. If there are multiple operations, the operator is given immediately after its second operand; so the expression written “3 − 4 + 5” would be written “3 4 − 5 +” first subtract 4 from 3, then add 5 to that.

Transform the algebraic expression with brackets into RPN form.

You can assume that for the test cases below only single letters will be used, brackets [] will not be used and each expression has only one RPN form (no expressions like a*b*c)

Input Format

The first line contains t, the number of test cases (less then 100).

Followed by t lines, containing an expression to be translated to RPN form, where the length of the expression is less then 400.

Output Format

The expressions in RPN form, one per line.

Example

Sample Input

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

Sample Output

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

Solution – Transform The Expression

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
	int test;
	cin>>test;
	while(test--)
	{
	    string s;
	    cin>>s;
	    vector <char>v;
	    for(int i=0;i<s.length();i++)
	    {
	        if(s[i]!=')'&&(isalpha(s[i])==0)&&s[i]!='(')
	        v.push_back(s[i]);
	        else if(s[i]!='('&&s[i]!=')')
	        cout<<s[i];
	        else if(s[i]==')')
	        {
    	        cout<<v.back();
    	        v.pop_back();
	        }
	    }
	    //cout<<v[3];
	    /*for (auto& it : v) {
  
        // Print the values
        cout << it <<;
        }*/
	    cout<<"\n";
	}
	return 0;
}

Python

# cook your dish here
for _ in range(int(input())):
    t = []
    st = []
    for i in input():
        if i.isalpha():
            t.append(i)
        elif i == ')':
            t.append(st.pop())
        elif i == '(':
            pass
        else:
            st.append(i)
    print("".join(t))

Java

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner s = new Scanner(System.in);
		int testCases = s.nextInt();
		while( testCases-- > 0 ){
		    String expr = s.next();
		    
		    Stack<Character> charStack = new Stack<>();
		    
		    String validString = getPostFixExpr(charStack,expr);
		    System.out.println(validString);
		    
		}
	}
	
	public static int priority(char ch){
	    switch(ch) {
	        case '+':
	        case '-': return 1;
	        
	        case '*':
	        case '/':return 2;
	        
	        case '^':return 3;
	            
	    }
	    return -1;
	}
	
	public static String getPostFixExpr( Stack<Character> temp , String expr ){
	    String postfix = "";
	    
	    int i = 0;
	    while(i < expr.length()){
	        if( expr.charAt(i) >= 'a' && expr.charAt(i) <= 'z' ){
	            postfix+=expr.charAt(i);
	        }else if( expr.charAt(i) == '(' ){
	            temp.push( expr.charAt(i) );
	        }else if( expr.charAt(i) == ')' ){
	            while( temp.peek() != '(' && !temp.isEmpty() ){
	                postfix+= temp.pop();
	            }
	            
	            if( temp.peek() == '(' ){
	                temp.pop();
	            }
	        }else 
	        {
	            while( ( priority(expr.charAt(i)) <= priority(temp.peek() ) ) && !temp.isEmpty() ){
	                postfix+=temp.pop();
	            }
	            
	            temp.push(expr.charAt(i));
	        }
	        i++;
	    }
	    return postfix;
	}
}

Disclaimer: The above Problem (Transform The Expression) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.