Arithmetic Expressions

In this series i will introduce some problem and algorithms for solving them

problem 1:

Evaluate the value of an arithmetic expression in Reverse Polish Notation .
Valid operators a re + , −, ∗ , /. Each operand may be an integer or another expression .
Some examples :
[ " 2 " , " 1 " , "+ " , " 3 " , " ∗ " ] −> ( ( 2 + 1) ∗ 3) −> 9
[ " 4 " , " 13 " , " 5 " , "/ " , "+ " ] −> (4 + (1 3 / 5) ) −> 6







import java.util.Stack;

/**
 * 
 * @author Mohamed Fawzy
 * @copyright GPL
 */
public class ArithmaticExpression {
 
 public static int evalRPN(String[] tokens){
  int returnValue=0;
  String operations = "+-*/"; // All Arithmatic operations
  // we push Expression and values into statck then return them back based on priroity for it 
  Stack<String> stack = new Stack<String>();
  for(String t: tokens){
   if(!operations.contains(t)){
    stack.push(t);
   }else{
    int a = Integer.valueOf(stack.pop());
    int b = Integer.valueOf(stack.pop());
    switch(t){
     case "+":
     stack.push(String.valueOf(a+b));
      break;
     case "-":
      stack.push(String.valueOf(a-b));
      break;
     case "*":
      stack.push(String.valueOf(a*b));
      break;
     case "/":
      stack.push(String.valueOf(a/b));
      break;
     
    }
   }
  }
  returnValue = Integer.valueOf(stack.pop());
  return returnValue;
 }
}


Test Case:



public class ArithmaticExpressionTest {
 
 public static void main(String[] args){
  String[] tokens = new String[] {"2","1","+","3","*"};
  ArithmaticExpression ae = new ArithmaticExpression();
  System.out.println(ae.evalRPN(tokens));
 }
}







You can find more at here : https://github.com/MohamedFawzy/AlgorithmsForInterview
Bye !

Comments

Popular Posts