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 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.
/*
* Java Program to Evaluate an Expression using Stacks
*/
import java.util.*;
public class EvaluateExpressionUsingStacks
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Create stacks for operators and operands */
Stack<Integer> op = new Stack<Integer>();
Stack<Double> val = new Stack<Double>();
/* Create temporary stacks for operators and operands */
Stack<Integer> optmp = new Stack<Integer>();
Stack<Double> valtmp = new Stack<Double>();
/* Accept expression */
System.out.println("Evaluation Of Arithmetic Expression Using Stacks Test\n");
System.out.println("Enter expression\n");
String input = scan.next();
input = "0" + input;
input = input.replaceAll("-","+-");
/* Store operands and operators in respective stacks */
String temp = "";
for (int i = 0;i < input.length();i++)
{
char ch = input.charAt(i);
if (ch == '-')
temp = "-" + temp;
else if (ch != '+' && ch != '*' && ch != '/')
temp = temp + ch;
else
{
val.push(Double.parseDouble(temp));
op.push((int)ch);
temp = "";
}
}
val.push(Double.parseDouble(temp));
/* Create char array of operators as per precedence */
/* -ve sign is already taken care of while storing */
char operators[] = {'/','*','+'};
/* Evaluation of expression */
for (int i = 0; i < 3; i++)
{
boolean it = false;
while (!op.isEmpty())
{
int optr = op.pop();
double v1 = val.pop();
double v2 = val.pop();
if (optr == operators[i])
{
/* if operator matches evaluate and store in temporary stack */
if (i == 0)
{
valtmp.push(v2 / v1);
it = true;
break;
}
else if (i == 1)
{
valtmp.push(v2 * v1);
it = true;
break;
}
else if (i == 2)
{
valtmp.push(v2 + v1);
it = true;
break;
}
}
else
{
valtmp.push(v1);
val.push(v2);
optmp.push(optr);
}
}
/* Push back all elements from temporary stacks to main stacks */
while (!valtmp.isEmpty())
val.push(valtmp.pop());
while (!optmp.isEmpty())
op.push(optmp.pop());
/* Iterate again for same operator */
if (it)
i--;
}
System.out.println("\nResult = "+val.pop());
}
}
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.
Related Posts:
- Check Data Structure Books
- Check Computer Science Books
- Practice Programming MCQs
- Practice Design & Analysis of Algorithms MCQ
- Check Programming Books