Skip to content

Instantly share code, notes, and snippets.

@Xe
Created May 25, 2012 04:22
Show Gist options
  • Save Xe/2785749 to your computer and use it in GitHub Desktop.
Save Xe/2785749 to your computer and use it in GitHub Desktop.

Infix to Postfix and Postfix Eval of BigIntegers

Due Thursday, May 24th by 11:59:59pm

Basic documentation is required, but no javadoc is necessary -- UNLESS YOU DID NOT SUCCESSFULLY UTILIZE JAVADOC ON YOUR LAST ASSIGNMENT For this assignment you will convert infix expressions to postfix expressions and then evaluate those postfix expressions. You will be given a table of symbols (A - Z) and their associated values to be used in evaluating expressions. The value for each symbol is to be considered a BigInteger. Negative values are also possible. Following this table you will be given a series of strings which will contain INFIX expressions which may be fully or partially parenthesized, but will be valid. The infix expressions will be given one per line and the series of expressions will be terminated by a line containing only a #. You may assume the following about the INFIX expressions:

  • the expressions will contain only the characters: A through Z, +, -, *, /, ^, (, ). NOTE: ^ represents the exponent operator, which is not supported in Java. You will need to make a call to BigInteger.pow( ) when applying this operator to operands to evaluate the postfix expression you create. Note that the parameter to BigInteger.pow( ) is an int. If you encounter a BigInteger exponent that is larger than Integer.MAX_VALUE, throw an exception, handle it and write the error to output. Program execution should then continue on to the next expression
  • the expressions will be correctly formed and all symbols used in the expressions will be defined.
  • the expressions will have no spaces between symbols and operators.
  • the values associated with symbols in the expressions will be positive or negative BigIntegers. Although the symbol values may be negative, the expressions will contain no unary negative operators.

The official name for the input file for this program is infix.txt (hard-code this into your program)-- all output is to the monitor. Here is a sample file you can use for testing -- it is by no means exhaustive -- make sure you add things to this file that properly test all categories of valid expressions -- the file is guaranteed to be well-formed and contain valid data and expressions throughout for the purposes of this assignment. It is permissible for you to collaborate with classmates on the postfix file you use for testing.

After printing out the INFIX expression, your program should convert the expression to POSTFIX form, using the algorithm discussed in class. Here are the lecture notes and code discussed in class After the conversion, the POSTFIX form of the expression should be printed out to the monitor. Finally, the POSTFIX expression should be evaluated (also using the algorithm discussed in class) and the final value of the expression should be printed out to the monitor. Here is sample output matching the infix.txt file shown above. The evaluation process will require a symbol table to be used to lookup the value associated with the expression symbols. This process should be repeated for each of the expressions. You may write your own Stack class or use the Java API! If you write your own, use the linked list version we did on the board in class.

Sample input file:

A -8
C 10
D 5
#
(A + C)*D
A+C * D
#

Sample output for the above input file:

Infix Expression: (A+C)*D
Postfix Equivalent: AC+D*
Expression value after postfix evaluation: 10

Infix Expression: A+C*D
Postfix Equivalent: ACD*+
Expression value after postfix evaluation: 42

To turn in:

Turn in a zip file named with your last name, followed by the first initial of your first name, followed by hw4 hw4 (e.g. armstrongehw4.zip ). Include all source and the robust input file you built and used to test your program. Name the file that contains the mane method and drives the program: InfixPostfixTester. Note that the InfixPostfixTester class should not do any conversions or calculations. You can use it to read in the data from the input file, but no work should be done on the data by the InfixPostfixTester class.

public class InfixPostfixTester {
/**
* @param args
*/
public static void main(String[] args) {
//Like you said, this should not do any conversions.
StackTester.main(args);
}
}
A -8
C 10
D 5
#
A+C*D
import java.io.IOException;
//taken from below as the converter supplied failed. It gave back infix expressions.
// http://www.java-forums.org/java-lang/7557-how-convert-infix-arithmetic-expressions-postfix.html
public class InToPost {
private Stack theStack;
private String input;
private String output = "";
public InToPost(String in) {
input = in;
int stackSize = input.length();
theStack = new Stack(stackSize);
}
//Had to add support for '^'
public String doTrans() {
for (int j = 0; j < input.length(); j++) {
char ch = input.charAt(j);
switch (ch) {
case '+':
case '-':
gotOper(ch, 1);
break; // (precedence 1)
case '*': // it's * or /
case '/':
gotOper(ch, 2); // go pop operators
break; // (precedence 2)
case '^':
gotOper(ch, 2);
break;
case '(': // it's a left paren
theStack.push(ch); // push it
break;
case ')': // it's a right paren
gotParen(ch); // go pop operators
break;
default: // must be an operand
output = output + ch; // write it to output
break;
}
}
while (!theStack.isEmpty()) {
output = output + theStack.pop();
}
//System.out.println(output);
return output; // return postfix
}
public void gotOper(char opThis, int prec1) {
while (!theStack.isEmpty()) {
char opTop = theStack.pop();
if (opTop == '(') {
theStack.push(opTop);
break;
}// it's an operator
else {// precedence of new op
int prec2;
if (opTop == '+' || opTop == '-')
prec2 = 1;
else
prec2 = 2; if (prec2 < prec1) // if prec of new op less
{ // than prec of old
theStack.push(opTop); // save newly-popped op
break;
} else
// prec of new not less
output = output + opTop; // than prec of old
}
}
theStack.push(opThis);
}
public void gotParen(char ch){
while (!theStack.isEmpty()) {
char chx = theStack.pop();
if (chx == '(')
break;
else
output = output + chx;
}
}
public static void main(String[] args) throws IOException {
String input = "1+2*4/5-7+3/6";
String output;
InToPost theTrans = new InToPost(input);
output = theTrans.doTrans();
System.out.println("Postfix is " + output + '\n');
}
class Stack {
private int maxSize;
private char[] stackArray;
private int top;
public Stack(int max) {
maxSize = max;
stackArray = new char[maxSize];
top = -1;
}
public void push(char j) {
stackArray[++top] = j;
}
public char pop() {
return stackArray[top--];
}
public char peek() {
return stackArray[top];
}
public boolean isEmpty() {
return (top == -1);
}
}
}
public class LinkedStack<E> {
private class Node<F> {
F data;
Node<F> next;
public Node(F data, Node<F> next) {
this.data = data;
this.next = next;
}
}
private Node<E> head;
public LinkedStack() {
head = null;
}
public void push(E data) {
Node<E> newNode = new Node<E>(data, head);
head = newNode;
}
public E peek() {
return head == null ? null : head.data;
}
public E pop() {
E ret = head.data;
head = head.next;
return ret;
}
public void nuke() {
head = null;
}
public boolean isEmpty() {
return head == null;
}
}
sam@fluttershy:~/Code/PostfixEval$ cd bin; java StackTester ../test1.txt ; cd ..
Processing symbol table
Storing symbol [A]
Index should be 0
Storing symbol [C]
Index should be 2
Storing symbol [D]
Index should be 3
Processing infix expressions
Infix expression: A+C*D
A
A+
A+C
A+C*
A+C*D
Postfix expression: A+C*D
import java.io.*;
import java.math.BigInteger;
import java.util.LinkedList;
public class StackTester
{
public static void main(String[] args)
{
String fileName = args.length > 0 ? args[0] :"/home/sam/Code/PostfixEval/test1.txt";
//**************************************************
try
{
FileInputStream fstream = new FileInputStream(fileName);
DataInputStream in = new DataInputStream(fstream);
BufferedReader br = new BufferedReader( new InputStreamReader(in));
String strLine;
//BigInteger[] symbols = new BigInteger[26];
LinkedList<BigInteger> symbols = new LinkedList<BigInteger>();
for(int derp = 0; derp < 26; derp++) {
symbols.add(derp, null);
}
boolean symTable = true; //reading symbol table
boolean infixData = false; // reading infix expressions
System.out.println("Processing symbol table");
while((strLine = br.readLine()) != null)
{
strLine = strLine.trim(); // trim any leading or trailing spaces
if(strLine.length() == 0)
{
continue; //skips empty lines
}
if(strLine.startsWith("#")) //Using a hash to separate the symbols definition and the expressions
{
if(!infixData)
{
System.out.println("\n Processing infix expressions\n");
symTable = false;
infixData = true;
}
continue; //so continue to the next string
}
if(symTable) // processes symbol table data
{
String delims = " ";//splits on 1 or more spaces
String[] tokens = strLine.split(delims);
System.out.println("Storing symbol [" + tokens[0] + "] - " + tokens[1]);
int index = tokens[0].charAt(0) - 'A'; //"hashing" function
//System.out.printf("Index should be %d\n", index);
BigInteger derp = new BigInteger(tokens[1]);
symbols.add(index, derp);
}
//Process the expressions as they come
if(infixData) // process infix expressions
{
System.out.printf("Infix expression: %s\n", strLine);
String postfixExpression = "";
InToPost converter = new InToPost(strLine);
postfixExpression = converter.doTrans();
System.out.printf("Postfix expression: %s\nNow parsing it\n", postfixExpression);
//Okay, so, now we've got the expression in the thing. Now to evaluate it.
LinkedStack<BigInteger> stack = new LinkedStack<BigInteger>();
boolean divByZero = false;
for(char c : postfixExpression.toCharArray()) {
if(isOperand(c)) {
stack.push(symbols.get(c-'A'));
} else if(isOperator(c)) {
BigInteger right = stack.pop();
BigInteger left = stack.pop();
if(right == null || left == null) {
break;
}
if(c == '+') { //Do adding
stack.push(left.add(right));
} else if(c == '-') { //Do Subtraction
stack.push(left.subtract(right));
} else if(c == '*') { //multiply
stack.push(left.multiply(right));
} else if(c == '/') { //divide
if (right.intValue() == 0) {
//System.out.println("Will not divide by zero.");
divByZero = true;
break;
}
stack.push(left.divide(right));
} else if(c == '^') {
stack.push(left.pow(right.intValue()));
}
}
}
System.out.printf("Got this: %s\n\n", divByZero ? "Divide by zero error, nice try" : stack.pop());
}
}
}
catch(Exception e)
{
System.err.println("Error: " + e.getMessage());
e.printStackTrace();
}
}
private static boolean isOperand (char cIn) {
return (cIn >= 'A' && cIn <= 'Z');
}
private static boolean isOperator (char cIn) {
return cIn == '^' || cIn == '*' || cIn == '/' || cIn == '+' || cIn == '-';
}
}
A -8
B 50
C 10
D 5
E 50000
F 0
#
A+C*D
(A+C)*D
C^E
E/F
((A+C*D)-F+(B-C))
C^E^E
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment