Stack Assignment Objective: to be familiar with stack operations and application
ID: 3553547 • Letter: S
Question
Stack Assignment
Objective: to be familiar with stack operations and applications
Requirements: (a) Implement a Java program that take in an infix expression from the user and output the expression in postfix notation. (b) [15 points bonus] If all the operands in the input are numeric, then your program should evaluate the expression and display its value.
Hints: detail algorithm for converting an infix expression to the equivalent postfix listed at: http://csis.pace.edu/~wolf/CS122/infix-postfix.htm
Explanation / Answer
import java.util.Scanner;
import java.util.Stack;
public class Infix2Postfix {
private Stack<String> stack;
private String infixExp;
private String postfixExp = "";
public Infix2Postfix(String exp){
String str = "";
infixExp = exp;
stack = new Stack<String>();
for (int i=0;i<infixExp.length();i++){
/*
* If the character is a letter or a digit we append it to the postfix
* expression directly.
*/
str = infixExp.substring(i,i+1);
if(str.matches("[a-zA-Z]|\d"))
postfixExp += str;
else if (isOperator(str)){
/*
* If the stack is empty we directly push the current char into it.
*/
if (stack.isEmpty()){
stack.push(str);
}
else{
/*
* If the current character is an operator, we need to check the stack
* status then, if the stack top contains an operator with lower
* precedence, we push the current character in the stack else we pop
* the character from the stack and add it to the postfix string. This
* continues till we either find an operator with lower precedence in the
* stack or we find the stack to be empty.
*/
String stackTop = stack.peek();
while (getPrecedence(stackTop,str).equals(stackTop)&& !(stack.isEmpty())){
postfixExp += stack.pop();
if (!(stack.isEmpty()))
stackTop = stack.peek();
}
stack.push(str);
}
}
}
// In the end just append all the operators from the stack to the postfix expression.
while(!(stack.isEmpty()))
postfixExp += stack.pop();
// Print out the postfix expression
System.out.println("The postfix form of the expression you entered is: " + postfixExp);
}
/*
* Returns true if 'ch' is an operator, false o/w
*/
private boolean isOperator(String ch){
String operators = "*/%+-";
if (operators.indexOf(ch) != -1)
return true;
else
return false;
}
/*
* Returns the operator with higher precedence among 'op1' & 'op2', if they have equal
* precedence, the first operator in the argument list (op1) is returned.
*/
private String getPrecedence(String op1, String op2){
String multiplicativeOps = "*/%";
String additiveOps = "+-";
if ((multiplicativeOps.indexOf(op1) != -1) && (additiveOps.indexOf(op2) != -1))
return op1;
else if ((multiplicativeOps.indexOf(op2) != -1) && (additiveOps.indexOf(op1) != -1))
return op2;
else if((multiplicativeOps.indexOf(op1) != -1) && (multiplicativeOps.indexOf(op2) != -1))
return op1;
else
return op1;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.