Write a program to generate RPN expression

Replies

• 

  pradeep_agrawal

  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
• 

  pradeep_agrawal

  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
• 

  sookie

  @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 stack=new Stack();
           String newSubExpr =null;
           int stackLength=0;
   
           for(int i=0;i4 && 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 !
• 

  pradeep_agrawal

  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
• 

  pradeep_agrawal

  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
• 

  sookie

  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 stack=new Stack();
           String newSubExpr =null;
           int stackLength=0;
   
           for(int i=0;i4 && 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.