ONP - Editorial [Transform the Expression]

#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.

  1. ‘(’ → Count = 1
  2. ‘(’ → Count = 2
  3. solution[0] = ‘a’
  4. stack ← ‘minus’ symbol
  5. solution1 = ‘b’
  6. Encounter ‘)’, count = 1, push stack top item into soln.
  7. solution2 = stack(top item)
  8. encounter symbol ‘multiplication’ ← push to stack
  9. ‘(’ → count = 2
  10. steps 3 to 5 repeated somewhat [the division sign: c/d was pushed to stack]
  11. encountered ‘)’ remove top item from stack ‘/’ and push to solution[5] & count = 1
  12. 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.
  13. 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

5 Likes

@admin please take a look.

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;
}

}

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

yashaswini1996
yes,we can use vector.

@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.

1 Like

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

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;
}

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.

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));
		}
		
	}
}

}

Great explanation!

Test cases are passing but WA on submission.

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

can someone please tell me the problem in this code?

#include <bits/stdc++.h>

using namespace std;

int pre(char c){
if(c==’+’ || c==’-’){
return 1;
}
if(c==’*’ || c==’/’){
return 2;
}
if(c==’^’){
return 3;
}

    return 0;

}

int main() {
// your code goes here
int a;
string b;
cin>>a;

while(a--){
    cin>>b;
    stack <char> s;
    int i=0;
    while(b[i]!='\0'){
        if(b[i]=='('){
            s.push(b[i]);
        }
        if(isalpha(b[i])){
            cout<<b[i];
        }
        if(!isalpha(b[i]) && b[i]!='(' && b[i]!=')'){
            while(pre(b[i])<=pre(s.top())){
                 cout<<s.top();
                 s.pop();
            }
            s.push(b[i]);
        }

        if(b[i]==')'){
            while(s.top()!='('){
                 cout<<s.top();
                 s.pop();
                }
                s.pop();
        }

        i++;
    }
    
    cout<<endl;


}


return 0;

}