Tuesday, September 2, 2008

infix to postfix

/*
Postfix.java - this program coverts an infix expression to a postfix expression, and evaluates it. Infix expressions must be typed with spaces between all numbers and operators.
Name: Alexis Dekle
Course: CPSC 215
Date: March 3, 2005
*/
import java.io.*;
import java.util.*;
public class Postfix
{
private static Stack operators = new Stack();
private static Stack operands = new Stack();

public static void main(String argv[]) throws IOException
{
String infix;

//create an input stream object
BufferedReader keyboard = new BufferedReader (new InputStreamReader(System.in));

//get input from user
System.out.print("\nEnter the algebraic expression in infix: ");
infix = keyboard.readLine();

//output as postfix
System.out.println("The expression in postfix is:" + toPostfix(infix));

//get answer
System.out.println("The answer to the equation is: " + evaluate(toPostfix(infix)) + "\n");
}

private static String toPostfix(String infix)
//converts an infix expression to postfix
{
StringTokenizer s = new StringTokenizer(infix);
//divides the input into tokens
String symbol, postfix = "";
while (s.hasMoreTokens())
//while there is input to be read
{
symbol = s.nextToken();
//if it's a number, add it to the string
if (Character.isDigit(symbol.charAt(0)))
postfix = postfix + " " + (Integer.parseInt(symbol));
else if (symbol.equals("("))
//push (
{
Character operator = new Character('(');
operators.push(operator);
}
else if (symbol.equals(")"))
//push everything back to (
{
while (((Character)operators.peek()).charValue() != '(')
{
postfix = postfix + " " + operators.pop();
}
operators.pop();
}
else
//print operators occurring before it that have greater precedence
{
while (!operators.empty() && !(operators.peek()).equals("(") && prec(symbol.charAt(0)) <= prec(((Character)operators.peek()).charValue()))
postfix = postfix + " " + operators.pop();
Character operator = new Character(symbol.charAt(0));
operators.push(operator);
}
}
while (!operators.empty())
postfix = postfix + " " + operators.pop();
return postfix;
}

private static int evaluate(String postfix)
{
StringTokenizer s = new StringTokenizer(postfix);
//divides the input into tokens
int value;
String symbol;
while (s.hasMoreTokens())
{
symbol = s.nextToken();
if (Character.isDigit(symbol.charAt(0)))
//if it's a number, push it
{
Integer operand = new Integer(Integer.parseInt(symbol));
operands.push(operand);
}
else //if it's an operator, operate on the previous two operands
{
int op2 = ((Integer)operands.pop()).intValue();
int op1 = ((Integer)operands.pop()).intValue();
int result = 0;
switch(symbol.charAt(0))
{
case '*': {result = op1 * op2; break;}
case '+': {result = op1 + op2; break;}
case '-': {result = op1 - op2; break;}
case '/': {result = op1 / op2; break;}
case '%': {result = op1 % op2; break;}
}
Integer operand = new Integer(result);
operands.push(operand);
}
}
value = ((Integer)operands.pop()).intValue();
return value;
}

private static int prec(char x)
{
if (x == '+' x == '-')
return 1;
if (x == '*' x == '/' x == '%')
return 2;
return 0;
}
}

No comments: