CrazyEngineers
CrazyEngineers

  • Write a program to generate RPN expression

    sookie

    sookie

    @sookie-T06sFW
    Updated: Oct 26, 2024
    Views: 1.4K
    OK, this may be many might be aware of (atleast CS?IT engineers)

    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

    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

    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+^*

    Source: <a href="https://www.codechef.com/problems/ONP/" target="_blank" rel="nofollow noopener noreferrer">ONP Problem | CodeChef</a>

    Thanks for giving a try! I will also come up with my program just stuck up at present.
    0
    Replies
Howdy guest!
Dear guest, you must be logged-in to participate on CrazyEngineers. We would love to have you as a member of our community. Consider creating an account or login.
Replies

  • pradeep_agrawal

    Member • Aug 23, 2009

    Find below my sample code for given problem statement.

    #include "stdio.h"

#define MAX_EXPRESSION_SIZE 400

typedef enum { OPERAND = 0, OPERATOR, BRACKET, STR } datatype_t;

typedef union {
  char ch;
  char str[MAX_EXPRESSION_SIZE];
} data_t;

typedef struct node {
  datatype_t datatype;
  data_t data;
  struct node *prev;
  struct node *next;
} node_t;

typedef struct {
  node_t* pHead;
  node_t* pTail;
} stack_t;


node_t* createnewelement(datatype_t datatype, data_t data) {
  node_t *newnode = (node_t*)malloc(sizeof(node_t));
  newnode->datatype = datatype;
  newnode->data = data;
  newnode->prev = NULL;
  newnode->next = NULL;
  return newnode;
}


void pushtostack(stack_t* stack, node_t* newelement) {
  if(stack->pHead) {
    stack->pTail->next = newelement;
    newelement->prev = stack->pTail;
    stack->pTail = newelement;
  } else {
    stack->pHead = newelement;
    stack->pTail = newelement;
  }
}


node_t* popfromstack(stack_t* stack) {
  node_t *lastelement = NULL;
  if(stack->pHead == NULL) {
    printf("Empty list\n");
    return NULL;
  } else {
    lastelement = stack->pTail;
    stack->pTail = stack->pTail->prev;
    if(stack->pTail == NULL) {
      stack->pHead = NULL;
    }
    return lastelement;
  }
}


void getRPN(char* expression, char* rpn) {
  int exp_len = strlen(expression);
  stack_t stack = { 0 };
  node_t* tempn = NULL;
  node_t* tempn1 = NULL;
  node_t* tempn2 = NULL;
  node_t* tempn3 = NULL;
  node_t* tempn4 = NULL;
  datatype_t tempdt = 0;
  data_t tempd = { 0 };
  int len = 0;
  int i = 0;

  for(i = 0; i < exp_len; i++) {
    if((expression[i] == ' ') || (expression[i] == '\t')) {
      //ignore whitespace
      continue;
    } else if((expression[i] == '+') || (expression[i] == '-') || (expression[i] == '*')
          || (expression[i] == '/') || (expression[i] == '^')) {
      tempdt = OPERATOR;
      tempd.ch = expression[i];
      pushtostack(&stack, createnewelement(tempdt, tempd));
    } else if(expression[i] == '(') {
      tempdt = BRACKET;
      tempd.ch = expression[i];
      pushtostack(&stack, createnewelement(tempdt, tempd));
    } else if(expression[i] == ')') {
      tempn1 = popfromstack(&stack);    //operand 2
      tempn2 = popfromstack(&stack);    //operator
      tempn3 = popfromstack(&stack);    //operand 1
      tempn4 = popfromstack(&stack);    //bracket ignore

      tempdt = STR;

      len = 0;
      if(tempn3->datatype == OPERAND) {
        tempd.str[0] = tempn3->data.ch;
        tempd.str[1] = '\0';
        len++;
      } else {
        strcpy(tempd.str, tempn3->data.str);
        len = strlen(tempd.str);
      }

      if(tempn1->datatype == OPERAND) {
        tempd.str[len] = tempn1->data.ch;
        tempd.str[len + 1] = '\0';
        len++;
      } else {
        strcat(tempd.str, tempn1->data.str);
        len = strlen(tempd.str);
      }

      tempd.str[len] = tempn2->data.ch;
      tempd.str[len + 1] = '\0';

      pushtostack(&stack, createnewelement(tempdt, tempd));

      free(tempn1);
      free(tempn2);
      free(tempn3);
      free(tempn4);
    } else {
      tempdt = OPERAND;
      tempd.ch = expression[i];
      pushtostack(&stack, createnewelement(tempdt, tempd));
    }
  }

  tempn = popfromstack(&stack);
  strcpy(rpn, tempn->data.str);
  free(tempn);
}


int main() {
  char** expressions = NULL;
  char rpn[MAX_EXPRESSION_SIZE] = { 0 };
  int exp_count = 0;
  int result = 0;
  int i = 0;

  //get abd validate number of expressions
  scanf("%d", &exp_count);
  getchar();    //to eliminate new line character from input stream
  if(exp_count <= 0) {
    printf("Invalid number of expressions\n");
    return 0;
  }

  //get expressions
  expressions = (char**)malloc(sizeof(char*)*exp_count);
  for(i = 0; i < exp_count; i++) {
    expressions[i] = (char*)malloc(sizeof(char)*MAX_EXPRESSION_SIZE);
    gets(expressions[i]);
    while(expressions[i][0] == '\0') {
      gets(expressions[i]);
    }
  }

  //get and print RPN for each expression
  for(i = 0; i < exp_count; i++) {
    getRPN(expressions[i], rpn);
    printf("%s\n", rpn);
    free(expressions[i]);
  }
  free(expressions);

  return 0;
}
    Compile the file with above code and run as:
    a.exe < input.txt > output.txt [on windows]
    a.out < input.txt > output.txt [on linux]

    Here,
    a.exe or a.out are the executables generated after compilation

    input.txt is the file containing input, e.g., for given example in problem input.txt will be:
    3
    (a+(b*c))
    ((a+b)*(z+x))
    ((a+t)*((b+(a+c))^(c+d)))

    output.txt is the output file containing result, for above input output.txt will contain:
    abc*+
    ab+zx+*
    at+bac++cd+^*

    -Pradeep
    Are you sure? This action cannot be undone.
    Cancel

  • pradeep_agrawal

    Member • Aug 23, 2009

    The above code works as per the given problem statement but have below limitations:
    1. Does not give suitable output/error for invalid expressions
    2. Need any operation to be specified under brackets, e.g., "a+b+c" need to be given as "((a+b)+c).
    3. Consider only () as bracket and not {} and [].
    4. Does not consider the precedence of operator +, -, *, /, and ^.

    The next level of this problem will be to remove this limitations from the code.

    -Pradeep
    Are you sure? This action cannot be undone.
    Cancel

  • sookie

    Member • Aug 23, 2009

    @Pradeep Thanks for your reply.

    Here goes my program in Java. Please check and review for improvements if it is failing for any expressions. I am very bad in testing my own program. 😉

    package myjava;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
/**
 *
 * @author sookie
 */
public class TransformIntoRPN {
 
 
    public static void main(String[] args) throws IOException{
 
       /* Enter the number of expressions 'n' for which you want to run this program for */         
        BufferedReader bin = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bin.readLine());
 
        for(int i = 1; i <= n; i++){
            transformIntoRPN(bin.readLine());           
        }
    }
    /* Method to transform the given expression into RPN */
    private static void transformIntoRPN(String expression) {
         Stack<String> stack=new Stack<String>();
         String newSubExpr =null;
         int stackLength=0;
 
         for(int i=0;i<expression.length();i++){
 
             /* pushes every character in the string on the stack */             
             stack.push(expression.substring(i,i+1));
             stackLength=stack.size();
 
             /* If stack cntains ')' bracket at the top , transformation starts */
             if(!stack.empty() && stack.size()>4 && expression.substring(i,i+1).equals(")")){
 
              newSubExpr=stack.get(stackLength-4)+stack.get(stackLength-2)+stack.get(stackLength-3);
 
               stack.removeElementAt(stackLength-1); //removes ')'
               stack.removeElementAt(stackLength-2); //removes operand 2
               stack.removeElementAt(stackLength-3); //removes operator
               stack.removeElementAt(stackLength-4); //removes operand 1
               stack.removeElementAt(stackLength-5); //removes '('
               stack.push(newSubExpr);
               }
 
         }
 
         /* Finally pops out the last element(RPN expression) remained in the stack at the end */
         if(!stack.empty()){
             System.out.println(stack.pop());
         }         
    }
}
    Output:
    3
    (a+(b*c))
    abc*+
    ((a+b)*(z+x))
    ab+zx+*
    ((a+t)*((b+(a+c))^(c+d)))
    at+bac++cd+^*
    @Pradeep Regarding limitations pointed out by you -

    Brackets & precedence : good thing, I will see if I can add that into my above program also. Do we need to consider only [], (), { } type of brackets only or all kind of brackets(e.g. there is one bar brackets also 😕) . For precedence of operators - what all operators we need to consider? Can you provide some sample expressions for above issues?

    Thanks !
    Are you sure? This action cannot be undone.
    Cancel

  • pradeep_agrawal

    Member • Aug 24, 2009

    sookie
    Here goes my program in Java. Please check and review for improvements if it is failing for any expressions. I am very bad in testing my own program. 😉
    I looked into the code, it gives the correct output. But it display a strange behavior. When i give below input:

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

    It gives output as:

    abc*+
    ab+zx+*

    and skip the last expression. To fix this i have modified the main method as:
        public static void main(String[] args) throws IOException {
        /* Enter the number of expressions 'n' for which you want to run this program for */         
        BufferedReader bin = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bin.readLine());
        
        String expressions[] = new String[n];
        for(int i = 0; i < n; i++) {
            expressions[i] = bin.readLine();           
        }
        
        for(int i = 0; i < n; i++) {
            transformIntoRPN(expressions[i]);           
        }
    }
    Above code give output for all expressions.

    -Pradeep
    Are you sure? This action cannot be undone.
    Cancel

  • pradeep_agrawal

    Member • Aug 24, 2009

    sookie
    @Pradeep Regarding limitations pointed out by you -
    Brackets & precedence : good thing, I will see if I can add that into my above program also. Do we need to consider only [], (), { } type of brackets only or all kind of brackets(e.g. there is one bar brackets also 😕) . For precedence of operators - what all operators we need to consider? Can you provide some sample expressions for above issues?
    - A general mathematical expression support all expression, so we should consider all these.
    - For time being we can consider +, -, *, /, and ^. But it will be good to write a code where we can add more operator with minor changes.

    Example:
    If input is "a + b * c -[(d + e) * f]" then the output should be "abc*+de+f*-".

    -Pradeep
    Are you sure? This action cannot be undone.
    Cancel

  • sookie

    Member • Aug 24, 2009

    Hey thanks a lot man for correcting my program. You made me to recall a lesson once given by one of our corporate trainer that "While developing a software(here program only) always keep in my mind that the client is DUMB* Ha ha ! 😁

    Anyway, I have a doubt if I do in the following way, then also your 'n' inputs-at-a-time funda would work right? If not, Please tell how you are giving input ?
    package myjava;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class TransformIntoRPN{
public static void main(String[] args) throws IOException{
 
       /* Enter the number of expressions 'n' for which you want to run this program for */         
        BufferedReader bin = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bin.readLine());
 
        String expressions[] = new String[n];
        [COLOR=blue]for(int i = 0; i < n; i++) {[/COLOR]
[COLOR=blue]    expressions[i] = bin.readLine();  [/COLOR]
[COLOR=blue]    transformIntoRPN(expressions[i]);[/COLOR]
[COLOR=blue]}[/COLOR]
 
[COLOR=blue]/* for(int i = 0; i < n; i++) {[/COLOR]
[COLOR=blue]    transformIntoRPN(expressions[i]);           [/COLOR]
[COLOR=blue]}*/[/COLOR]
    }
    /* Method to transform the given expression into RPN */
    private static void transformIntoRPN(String expression) {
         Stack<String> stack=new Stack<String>();
         String newSubExpr =null;
         int stackLength=0;
 
         for(int i=0;i<expression.length();i++){
 
             /* pushes every character in the string on the stack */             
             stack.push(expression.substring(i,i+1));
             stackLength=stack.size();
 
             /* If stack cntains ')' bracket at the top , transformation starts */
             if(!stack.empty() && stack.size()>4 && expression.substring(i,i+1).equals(")")){
 
              newSubExpr=stack.get(stackLength-4)+stack.get(stackLength-2)+stack.get(stackLength-3);
 
               stack.removeElementAt(stackLength-1); //removes ')'
               stack.removeElementAt(stackLength-2); //removes operand 2
               stack.removeElementAt(stackLength-3); //removes operator
               stack.removeElementAt(stackLength-4); //removes operand 1
               stack.removeElementAt(stackLength-5); //removes '('
               stack.push(newSubExpr);
               }
 
         }
 
         /* Finally pops out the last element(RPN expression) remained in the stack at the end */
         if(!stack.empty()){
             System.out.println(stack.pop());
         }         
    }
}
    Output as:
    3
    (a+(b*c))
    ((a+b)*(z+x))
    ((a+t)*((b+(a+c))^(c+d)))
    abc*+
    ab+zx+*
    at+bac++cd+^*
    Thanks for the "Enhanced version of Write a program to generate RPN expression" problem 😉. Give some time to look into it.
    Are you sure? This action cannot be undone.
    Cancel
Home Channels Search Login Register