PLEASE GUYES EXPLAIN TO ME THIS ASSIGNMENT USING JAVA PROGRAM - ECLIPSE. Problem
ID: 3879186 • Letter: P
Question
PLEASE GUYES EXPLAIN TO ME THIS ASSIGNMENT USING JAVA PROGRAM - ECLIPSE.
Problem: You will implement a calculator program based on the stack-based algorithms given in class. These algorithms are reproduced below.
Your program prompts the user to enter an arithmetic expression (as a string) that can contain the symbols +, -, *, /, (, ) and the digits 0-9. To keep the problem (relatively) simple, numbers in the expression can only be one digit long.
Example:
5 + (6 – 2) * 8 – 9 / 3
is a valid input string.
Your program solves the arithmetic expression using the correct order of operations and prints the answer. (The answer to the expression above is 34.)
You may assume that the input string is always valid. Note that the input string may contain spaces.
Converting Infix to Postfix: The first task your program must perform is the conversion of the given infix expression into a postfix expression. Recall that infix means that the operator appears between two numbers whereas postfix means that the operator appears after the numbers.
Example:
5 + 3 – 2
is an infix expression. The equivalent postfix expression is:
5 3 + 2 –
Here is the algorithm for converting infix to postfix:
Start with an empty postfix expression and an empty stack.
Traverse the infix expression left to right:
If the current character is a digit,
Append digit to postfix expression.
If the current character is a ) symbol,
Pop the stack and append popped symbols to postfix expression until the ( symbol is at the top.
Pop the ( symbol.
If the current character is any other symbol (but not a space),
Pop the stack and append popped symbols to postfix expression until a symbol of lower priority is at the top, the ( symbol is at the top, or the stack is empty.
Push current character onto stack.
Pop the rest of the stack and append popped symbols to postfix expression.
Evaluating the Postfix Expression: Once you have a postfix expression, your program can evaluate it to find the answer using the following algorithm:
Start with an empty stack.
Traverse the postfix expression left to right:
If the current character is a digit,
Push digit onto stack.
If the current character is an operator,
Pop two digits off the stack and apply the operator to them in the proper order to get a result. (For example, if the symbol is – and you pop 4 and 7, in that order, then compute 7 – 4 to get the result 3.)
Push the result onto stack.
Pop the stack to get the answer.
Extra Credit: Enhance the program so that the arithmetic expression can contain any integer instead of only single-digit integers.
Explanation / Answer
/*Whole code is well commented so please create a class with name "ExpressionEveluation" and copy whole answer in your ide and execute
* Evaluation of any arithmetic expression includes two steps
* (1) Infix to Postfix conversion
* (2) Evaluation of postfix
*
* To do both the above operation we need Stack data Structure
* Stack: Stack is a linear Data Structure follow Last In First Out (LIFO) Order means
* the element Inserted last will be deleted first, three important operations on stack
* (a) push(val)=> insert the value to the stack
* (b) pop() => delete the top element from stack
* (c) peek()=> return top element without delete
* For more understanding please read about Stack Data Structure
*
* Now come to solution: (1) Infix to Postfix
* Steps are same as your given in problem statement
1.Start with an empty postfix expression and an empty stack.
2.Traverse the infix expression left to right:
3. If the current character is a digit,
4. Append digit to postfix expression.
5. If the current character is a ) symbol,
6. Pop the stack and append popped symbols to postfix expression until the ( symbol is at the top.
7.Pop the ( symbol.
8.If the current character is any other symbol (but not a space),
9.Pop the stack and append popped symbols to postfix expression until a symbol of lower priority is at the top, the ( symbol is at the top, or the stack is empty.
priority of symbols=> /=* > +=-
10.Push current character onto stack.
11.Pop the rest of the stack and append popped symbols to postfix expression.
*
Steps to evaluate Expression from your problem statement:
1.Start with an empty stack.
2.Traverse the postfix expression left to right:
3.If the current character is a digit,
4.Push digit onto stack.
5.If the current character is an operator,
6.Pop two digits off the stack and apply the operator to them in the proper order to get a result. (For example, if the symbol is – and you pop 4 and 7, in that order, then compute 7 – 4 to get the result 3.)
7.Push the result onto stack.
8.Pop the stack to get the answer.
*
*Sample Input: 5 + (6 - 2) * 8 - 9 / 3
*Sample OutPut:
Postfix exp: 562-8*+93/-
Final Result is : 34
*/
//To solve this problem ,I am going to use Stack provided by Java Collection
//Java Program to evaluate a arithmetic expression
import java.util.*;
import java.io.*;
public class ExpressionEveluation {
//Function to return priority of a given operator
// Higher returned value means higher priority
static int Priority(char ch)
{
switch (ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
}
return -1;
}
//Function to convert Infix expression to postfix expression
public static String infixToPostfix(String input)
{
//Instantiating Stack to store Character
Stack<Character> stack=new Stack<Character>();
String postfixExp="";
for(int i=0;i<input.length();i++)
{
char ch=input.charAt(i);
//If current character is white space the continue
if(ch==' ')
{
continue;
}
else if(ch>='0' && ch<='9') //If current character is digit add to postfixExp
{
postfixExp +=ch;
}
else if(ch=='(')
stack.add(ch);
else
{
if(ch==')')
{
//poping all the symbols until '(' comes
while (!stack.isEmpty() && stack.peek() != '(')
{
char top=stack.pop();
postfixExp +=top;
}
if (!stack.isEmpty() && stack.peek() != '(')
return "Invalid Expression"; // invalid expression
else
stack.pop();
}
else
{
while (!stack.isEmpty() && Priority(ch) <= Priority(stack.peek()))
postfixExp += stack.pop();
stack.push(ch);
}
}
}
//finally emptying stack
while(!stack.isEmpty())
{
char top=stack.pop();
postfixExp +=String.valueOf(top);
}
return postfixExp;
}
public static int postEval(String postfixExp)
{
//Instantiating Stack to store Character
Stack<Integer> stack=new Stack<Integer>();
for(int i=0;i<postfixExp.length();i++)
{
char ch=postfixExp.charAt(i);
if(ch>='0' && ch<='9')
{
//Getting integer value from ascii value
int x=(int)ch-48;
stack.add(x);
}
//in below four conditions getting top two elements from stack and doing calculation and adding result back to stack
else if(ch=='+')
{
int a=stack.pop();
int b=stack.pop();
int c=a+b;
stack.add(c);
}
else if(ch=='*')
{
int a=stack.pop();
int b=stack.pop();
int c=a*b;
stack.add(c);
}
else if(ch=='-')
{
int a=stack.pop();
int b=stack.pop();
int c=b-a;
stack.add(c);
}
else if(ch=='/')
{
int a=stack.pop();
int b=stack.pop();
int c=b/a;
stack.add(c);
}
}
int finalResult=stack.pop();
return finalResult;
}
public static void main(String[] args) throws IOException{
//Creating BufferedReader object to read input from user
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
//Reading input
String input=br.readLine();
//Calling infixToPostfix(input) which will convert infix expression to postfix expression
String postfixExp=infixToPostfix(input);
//Printing postfix expression
System.out.println("Postfix exp: "+postfixExp);
//Calling postEval(postfixExp) to evaluate expression
int resultOfExp=postEval(postfixExp);
System.out.println("Final Result is : "+resultOfExp);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.