Java Program to Evaluate an Expression using Stacks

This is a Java Program to evaluate an expression using stacks. Stack is an area of memory that holds all local variables and parameters used by any function and remembers the order in which functions are called so that function returns occur correctly. ‘push’ operation is used to add an element to stack and ‘pop’ operation is used to remove an element from stack. ‘peek’ operation is also implemented returning the value of the top element without removing it. The relation between the push and pop operations is such that the stack is a Last-In-First-Out (LIFO) data structure.
Here concept of stacks is applied to evaluate an arithmetic expression. This method of evaluation is commonly employed in calculators and many compilers for parsing the syntax of expressions, program blocks etc. before translating into low level code.

Here is the source code of the Java program to evaluate an arithmetic expression using stacks. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /*
  2.  *  Java Program to Evaluate an Expression using Stacks
  3.  */
  4.  
  5. import java.util.*;
  6.  
  7. public class EvaluateExpressionUsingStacks 
  8. {
  9.     public static void main(String[] args)
  10.     { 
  11.         Scanner scan = new Scanner(System.in);
  12.         /* Create stacks for operators and operands */
  13.         Stack<Integer> op  = new Stack<Integer>();
  14.         Stack<Double> val = new Stack<Double>();
  15.         /* Create temporary stacks for operators and operands */
  16.         Stack<Integer> optmp  = new Stack<Integer>();
  17.         Stack<Double> valtmp = new Stack<Double>();
  18.         /* Accept expression */
  19.         System.out.println("Evaluation Of Arithmetic Expression Using Stacks Test\n");
  20.         System.out.println("Enter expression\n");
  21.         String input = scan.next();
  22.         input = "0" + input;
  23.         input = input.replaceAll("-","+-");
  24.         /* Store operands and operators in respective stacks */
  25.         String temp = "";
  26.         for (int i = 0;i < input.length();i++)
  27.         {
  28.             char ch = input.charAt(i);
  29.             if (ch == '-')
  30.                 temp = "-" + temp;
  31.             else if (ch != '+' &&  ch != '*' && ch != '/')
  32.                temp = temp + ch;
  33.             else
  34.             {
  35.                 val.push(Double.parseDouble(temp));
  36.                 op.push((int)ch);
  37.                 temp = "";
  38.             }
  39.         }
  40.         val.push(Double.parseDouble(temp));
  41.         /* Create char array of operators as per precedence */
  42.         /* -ve sign is already taken care of while storing */
  43.         char operators[] = {'/','*','+'};
  44.         /* Evaluation of expression */
  45.         for (int i = 0; i < 3; i++)
  46.         {
  47.             boolean it = false;
  48.             while (!op.isEmpty())
  49.             {
  50.                 int optr = op.pop();
  51.                 double v1 = val.pop();
  52.                 double v2 = val.pop();
  53.                 if (optr == operators[i])
  54.                 {
  55.                     /* if operator matches evaluate and store in temporary stack */
  56.                     if (i == 0)
  57.                     {
  58.                         valtmp.push(v2 / v1);
  59.                         it = true;
  60.                         break;
  61.                     }
  62.                     else if (i == 1)
  63.                     {
  64.                         valtmp.push(v2 * v1);
  65.                         it = true;
  66.                         break;
  67.                     }
  68.                     else if (i == 2)
  69.                     {
  70.                         valtmp.push(v2 + v1);
  71.                         it = true;
  72.                         break;
  73.                     }                                        
  74.                 }
  75.                 else
  76.                 {
  77.                     valtmp.push(v1);
  78.                     val.push(v2);
  79.                     optmp.push(optr);
  80.                 }                
  81.             }    
  82.             /* Push back all elements from temporary stacks to main stacks */            
  83.             while (!valtmp.isEmpty())
  84.                 val.push(valtmp.pop());
  85.             while (!optmp.isEmpty())
  86.                 op.push(optmp.pop());
  87.             /* Iterate again for same operator */
  88.             if (it)
  89.                 i--;                            
  90.         }    
  91.         System.out.println("\nResult = "+val.pop());        
  92.     }
  93. }

Evaluation Of Arithmetic Expression Using Stacks Test
 
Enter expression
 
3*4+5*6-32/8+19/4*43+5-32+7-58/9+12*3-48/8-3/7+14/2+12*3+5
 
Result = 293.3769841269841
 
 
 
 
Evaluation Of Arithmetic Expression Using Stacks Test
 
Enter expression
 
32+45-23+45/13+28-4/32+51/17-49/3+157+2+4*45+3/4-6*5-48+13*12-42/12+24/162*94
 
Result = 500.17913105413106
 
 
 
Evaluation Of Arithmetic Expression Using Stacks Test
 
Enter expression
 
12.5*18+35.64/23.45+64.12-77.1+24/65+13.76+246.34-23*123+162.1+24*6-19+94
 
Result = -1973.890939806462

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.