/*
	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;
	}
}