ONP - Editorial [Transform the Expression]

aalok_sathe · January 30, 2015, 12:14am

#Problem Statement:
Link

Difficulty:
Cakewalk <–> Easy

Prerequisites: Concept of Stacks, Reverse Polish Notation

The Problem:

The problem finally boils down to:

You are given an algebraic expression
Operations over one-character variables
All expressions are closed by ‘(’ and ‘)’ brackets.
Keeping track of secondary expressions between one opening ‘(’ and its corresponding closing ‘)’
Thus tertiary expressions in between secondary brackets and so on…
Use of basic mathematical operation symbols (+ - / * ^ %)

Explanation:

All variables used in the problem are of length=1. It is assured that expressions are of type:simple.
Implies that there will be expressions only of the type a+b and not a+b+c.

Now, maintain a count. For your input expression to terminate, you have to come across a reverse bracket id est ‘)’. In other words, for every ( there has to be a ).
Thus you can start by taking in a character which you are sure is ‘(’.
Maintain a count and increment it for every ‘(’ that you find along the way and while this count is more than zero, you must take in and process the expression.
Now, a ‘(’ can be followed by either another ( or some variable, say ‘x’. Let’s say you have gone through one or more of these ‘(’ and have now come to a variable.
You shall then push this variable into a solution array of length [405].

After a variable, you will get an operator symbol. You have to sideline it temporarily for one step. In other words you will put it into a stack and pull it out after you take the next variable into consideration. Suppose the next variable was ‘y’ {initial was ‘x’, right?}. Let your expression be x#y where # is some operation symbol. After taking ing ‘x’ you expect a symbol and you push it into a stack. Then you expect a character y. You push the character into the solution array. And then comes the symbol.
The brackets are to be completely ignored for our answer.

Now take a different case.
Exempli gratia, ((a-b)***(c/d)). Now how will you cope with the multiplication sign which has no variables but two expressions to follow? This is why, a symbol must necessarily be pushed to the solution array only after encountering the ‘)’ closing bracket.
Now take this specific case according to how our algorithm will process it.

‘(’ --> Count = 1
‘(’ --> Count = 2
solution[0] = ‘a’
stack <-- ‘minus’ symbol
solution1 = ‘b’
Encounter ‘)’, count = 1, push stack top item into soln.
solution2 = stack(top item)
encounter symbol ‘multiplication’ <-- push to stack
‘(’ --> count = 2
steps 3 to 5 repeated somewhat [the division sign: c/d was pushed to stack]
encountered ‘)’ remove top item from stack ‘/’ and push to solution[5] & count = 1
encountered another ‘)’: now remember the multiplication symbol that we pushed… Now take that out from stack as it is the topmost item in our stack currently.
count becomes 0. terminate.

Let’s see how our solution array looks like.
ab-cd/*

General Algorithm:

initialize count=0;
input first character (which you know is a opening bracket ‘(’ for sure)
count ++
while count is greater than 0

do:

if next char is ‘(’ count ++
else if next char is {+ - / … etc} then put into stack
else if next char is ‘)’ count – and then pull out topmost item from stack and push to array.
(now only case left is variable alphabet): else directly push char to solution.

Solution

Editorialist solution can be found HERE

Editorial By @aalok_sathe

aalok_sathe · January 30, 2015, 8:57am

@admin please take a look.

nanhe · February 28, 2016, 2:52pm

please can anyone tell me what is wrong in this code

#include
using namespace std;
main()
{
int t,j=0,top=-1;
char a[400],stack[400],b[400];
cin>>t;
while(t–)
{
cin>>a;

	for(int i=0;a[i]!='\0';i++)
  {
        if( (a[i]=='(')||(a[i]=='+')||(a[i]=='-')||(a[i]=='*')||(a[i]=='/')||(a[i]=='^') )
        {
        	top++;
        	stack[top]=a[i];
    	    
        }
        else if(a[i]==')')
        {
    	   b[j]=stack[top];
    	   j++;
    	   top--;
    	   while(stack[top]!='(')
      	    {
      	   	b[j]=stack[top];
      	   j++;
			 }
      	   top--;
    	  
        }
       else
       {
  	       b[j]=a[i];
           j++;
          
       }
    }

   cout<<b<<endl;
   j=0,top=-1;
}

}

yashaswini1996 · February 28, 2016, 5:37pm

plz can anyone tell me whether we can make a code without using " #include "

nanhe · March 1, 2016, 7:06pm

yashaswini1996
yes,we can use vector.

ajay141164 · March 1, 2016, 7:27pm

@yashaswini1996
You can check my solution - https://www.codechef.com/viewsolution/9492252
I used stack (STL C++)
If you do not want to use STL you can impelement stack using an array.

samgrv · March 23, 2016, 12:16am

Can’t we do it using only stacks like making two stacks, one for operators and another for brackets?

paintbrush · January 4, 2017, 11:18am

It’s not necessary to use Stack for this problem. I solved this only using arrays. Here’s my code (In C++) -

 #include<iostream>
 using namespace std;
 int main()
 {
   	int t, count, i, j, k, n=0;
   	char x;
   	cin>> t;
	
	while (1)
	{
		char* A = new char[400];
		char* B = new char[400];
		char* C = new char[400];
		i = -1; j = -1; count = 0;
		cin >> x;
		if ( x == '(') count++;
		while (count > 0)
		{
			cin >> x;
			if (x == '(') count++; //case- open bracket
			else {
				if ((x == '+') || (x == '-') || (x == '*') || (x == '/') || (x == '^') || (x == '%')) //case- operand
				{
					B[count-1] = x;
				}
				else
				{
					if (x == ')') //case- close bracket
					{
						cout << B[count - 1];
						count--;
					}
					else
					{
						if (x == '\n') break; //case- newline character
						else cout << x;  //case- alphabet
					}
				}
			}
		}
		cout << '\n';
		delete[] A;
		delete[] B;
		delete[] C;
		n++;
		if (n == t) break;
	}
	return 0;
}

rajdeep2001 · May 15, 2017, 6:13pm

I tested my code with as many test cases as I could think of but it still shows wrong answer.
My code can be found here Solution

Please help me.

ayush_312 · June 28, 2017, 12:40pm

can’t find the problem in this code as i checked as many cases i can.
Can someone please explain the problem in this code.
import java.util.*;
import java.util.Scanner;

public class nka {

private static Scanner sc;

public static void main(String[] args) {
	sc = new Scanner(System.in);
	int testcase = sc.nextInt();
	String m ;
	char[] input;
	
	for(int i = 0;i<testcase+1;i++){
		System.out.println();
		m = sc.nextLine();
		input=m.toCharArray();
		ArrayList<Character> operator = new ArrayList<>(),output = new ArrayList<>();
		for(int j =0;j<m.length();j++){
			if(input[j] !='+'&& input[j] !='-'&& input[j] !='*'&& input[j] !='/'&& input[j] !=')'&& input[j] !='(' && input[j] !='^'){
				output.add(input[j]);
			}
			else{
				if(input[j] =='-'){
					if(!operator.isEmpty()&&operator.get(operator.size()-1)!='('){
					while(!operator.isEmpty()&& operator.get(operator.size()-1)=='+'||operator.get(operator.size()-1)=='^' || operator.get(operator.size()-1)=='/' ||operator.get(operator.size()-1)=='*'){
						output.add(operator.get(operator.size()-1));
						operator.remove(operator.get(operator.size()-1));
					}	
					operator.add(input[j]);
				}else
					operator.add(input[j]);
				}
				if(input[j] =='+'){
					if(!operator.isEmpty()&&operator.get(operator.size()-1)!='('){
					while(!operator.isEmpty()&&operator.get(operator.size()-1)=='^' || operator.get(operator.size()-1)=='/' ||operator.get(operator.size()-1)=='*'){
						output.add(operator.get(operator.size()-1));
						operator.remove(operator.get(operator.size()-1));
					}
					output.add(input[j]);
				}else
					operator.add(input[j]);
				}
				if(input[j] =='*'){
					if(!operator.isEmpty()&&operator.get(operator.size()-1)!='('){
					while(!operator.isEmpty()&&operator.get(operator.size()-1)=='^' || operator.get(operator.size()-1)=='/'){
						output.add(operator.get(operator.size()-1));
						operator.remove(operator.get(operator.size()-1));
					}
					operator.add(input[j]);
				}else
					operator.add(input[j]);
				}
				if(input[j] =='/'){
					if(!operator.isEmpty()&&operator.get(operator.size()-1)!='('){
					while(!operator.isEmpty()&&operator.get(operator.size()-1)=='^'){
						output.add(operator.get(operator.size()-1));
						operator.remove(operator.get(operator.size()-1));
					}
					operator.add(input[j]);
				}else
					operator.add(input[j]);
				}
				if(input[j] =='^'){
					operator.add(input[j]);
				}
				if(input[j] =='('){
					operator.add(input[j]);
				}
				if(input[j] ==')'){
					while(!operator.isEmpty()&&operator.get(operator.size()-1)!='('){
						output.add(operator.get(operator.size()-1));
						operator.remove(operator.get(operator.size()-1));
					}
					operator.remove(operator.get(operator.size()-1));
				}
			}
				
			
		}
		for(int j =operator.size()-1;j>=0;j--){
			output.add(operator.get(j));
			}
		for(int j =0;j<output.size();j++){
		System.out.print(output.get(j));
		}
		
	}
}

}

mr_nair · November 25, 2017, 4:15pm

Great explanation!

prembhai · December 30, 2017, 5:26pm

Test cases are passing but WA on submission.

https://www.codechef.com/viewsolution/16702597

can someone please tell me the problem in this code?