Using a Stack Requirements: converts and prints the equivalent postfix expressio
ID: 3536737 • Letter: U
Question
Using a Stack
Requirements:
converts and prints the equivalent postfix expression and then evaluates the expression. The expression from the user will only contain floating point numbers, left and right parenthesis, the arithmetic operators +, -, *, / and white space.
How to Proceed:
Make sure you have the array implementation or the linked implementation of the StackADT working.
Then code the algorithm below to read in a string and convert it to postfix notation.
Finally write the main( ) driver:
The driver will combine the three pieces of the project, the stack code, the infix-to-postfix converter and the postfix evaluator (found in the textbook, chapter 3). The driver should ask the user to enter an infix expression (using spaces between each token), print the equivalent postfix expression, call the code to evaluate the postfix expression and print the value. This should continue until the user decides to stop entering expressions.
Infix to Postfix
The following is an algorithm that can be used to convert an expression in infix notation to one in postfix, or RPN. This algorithm will work on any expression that uses simple binary operators and parenthesis, things get messy with unary operators or other non-binary ones. For this example, assume we're just using +, -, *, and /
To start with, assume we've got the infix expression in a string, and that we have a stack we're going to be using to help with the conversion. All we have to do is iterate through the string, checking each character, or token. There are four scenarios (ignore any white space character):
Operator: If the token is an operator, and there's nothing else on our stack, we push that operator onto the stack. If there is something on the stack, we compare the precedence of our current operator with the one on the stack, if the stack's is greater or equal to ours, we pop it and add it to our output string. If it's less than ours, we push our current operator and go on. We keep comparing the current operator to the stack until we hit the end of the stack, we hit a left parenthesis on the stack, or we find an operator on the stack with lower precedence than ours.
Left Parenthesis: If the token is a left parenthesis we simply push it onto the stack.
Right Parenthesis: If the token is a right parenthesis, we do a Multi-Pop! That is to say, we pop everything off the stack until we hit a left parenthesis or the end of the stack.
Operand: If the token is an operand we simply add it to our output string.
When all this is done with, we perform a Super-Pop!. Which means we pop every last thing off the stack. If everything went well, then the only things left should be operators. If there's a parenthesis left over, something's wrong. If there's an operand, you've pretty seriously messed up, since at no point in the algorithm do we put those on the stack.
Explanation / Answer
Hey, check the code here.
Then I ll do the desired modifications.
Rate if you like it.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;
public class InfixToPostfix {
// Associativity constants for operators
private static final int LEFT_ASSOC = 0;
private static final int RIGHT_ASSOC = 1;
// Supported operators
private static final Map<String, int[]> OPERATORS = new HashMap<String, int[]>();
static {
// Map<"token", []{precendence, associativity}>
OPERATORS.put("+", new int[] { 0, LEFT_ASSOC });
OPERATORS.put("-", new int[] { 0, LEFT_ASSOC });
OPERATORS.put("*", new int[] { 5, LEFT_ASSOC });
OPERATORS.put("/", new int[] { 5, LEFT_ASSOC });
OPERATORS.put("%", new int[] { 5, LEFT_ASSOC });
OPERATORS.put("^", new int[] { 10, RIGHT_ASSOC });
}
/**
* Test if a certain is an operator .
* @param token The token to be tested .
* @return True if token is an operator . Otherwise False .
*/
private static boolean isOperator(String token) {
return OPERATORS.containsKey(token);
}
/**
* Test the associativity of a certain operator token .
* @param token The token to be tested (needs to operator).
* @param type LEFT_ASSOC or RIGHT_ASSOC
* @return True if the tokenType equals the input parameter type .
*/
private static boolean isAssociative(String token, int type) {
if (!isOperator(token)) {
throw new IllegalArgumentException("Invalid token: " + token);
}
if (OPERATORS.get(token)[1] == type) {
return true;
}
return false;
}
/**
* Compare precendece of two operators.
* @param token1 The first operator .
* @param token2 The second operator .
* @return A negative number if token1 has a smaller precedence than token2,
* 0 if the precendences of the two tokens are equal, a positive number
* otherwise.
*/
private static final int cmpPrecedence(String token1, String token2) {
if (!isOperator(token1) || !isOperator(token2)) {
throw new IllegalArgumentException("Invalied tokens: " + token1
+ " " + token2);
}
return OPERATORS.get(token1)[0] - OPERATORS.get(token2)[0];
}
public static String[] infixToRPN(String[] inputTokens) {
ArrayList<String> out = new ArrayList<String>();
Stack<String> stack = new Stack<String>();
// For all the input tokens read the next token
for (String token : inputTokens) {
if (isOperator(token)) {
// If token is an operator (x)
while (!stack.empty() && isOperator(stack.peek())) {
// [S4]
if ((isAssociative(token, LEFT_ASSOC) && cmpPrecedence(
token, stack.peek()) <= 0)
|| (isAssociative(token, RIGHT_ASSOC) && cmpPrecedence(
token, stack.peek()) < 0)) {
out.add(stack.pop());
continue;
}
break;
}
// Push the new operator on the stack
stack.push(token);
} else if (token.equals("(")) {
stack.push(token);
} else if (token.equals(")")) {
while (!stack.empty() && !stack.peek().equals("(")) {
out.add(stack.pop());
}
stack.pop();
} else {
out.add(token);
}
}
while (!stack.empty()) {
out.add(stack.pop());
}
String[] output = new String[out.size()];
return out.toArray(output);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Enter an infix expression");
System.out.println("");
String inputString = scanner.nextLine();
String[] input = inputString.split(" ");
System.out.println("The corresponding postfix expression is");
String[] output = infixToRPN(input);
for (String token : output) {
System.out.print(token + " ");
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.