Write a program to generate RPN expression

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

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

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

sookieHere 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

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

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.