Evaluate a Postfix Expression Using a Singly Linked List

Question

I'm writing a program that asks the user for a postfix expression, and then outputs the result to the expression. I am attempting to do this using a Singly Linked List, and using the Adapter Pattern to create a stack.

The code for the SinglyLinkedList class, the LinkedStack class, and the Stack implementation are all straight out of a Data Structures book that I own. So the SinglyLinkedListTest class is the only one that has my own code in it (and has errors).

I've written a program that simply uses a stack to evaluate a postfix expression before, but I'm getting confused this time with the extra classes included.

I'm sure I have a ton of errors, but the most obvious ones to me are in my SinglyLinkedListTest class, every time I push a value onto the stack. I know the issue is that I am attempting to push Objects and characters onto the stack instead of the arguments that match push(E e), but I don't know how to alter my code to make this work.

Any suggestions or input would be greatly appreciated.

Here is my Stack Implementation:

package PostFix;

public interface Stack<E> 
{
    int size();

    boolean isEmpty();

    void push(E e);

    E pop();
}

Here is my LinkedStack class:

package PostFix;

public class LinkedStack <E> implements Stack<E>
{
    private SinglyLinkedList<E> list = new SinglyLinkedList<>();

    public LinkedStack()
    {

    }

    public int size()
    {
        return list.size();
    }

    public boolean isEmpty()
    {
        return list.isEmpty();
    }

    public void push(E e)
    {
        list.addFirst(e);
    }

    public E pop()
    {
        return list.removeFirst();
    }
}

Here is my SinglyLinkedList class:

package PostFix;

public class SinglyLinkedList<E>
{
    private static class Node<E>
    {
        private E element;
        private Node<E> next;

        public Node(E e, Node<E> n)
        {
            element = e;
            next = n;
        }

        public E getElement()
        {
            return element;
        }

        public Node<E> getNext()
        {
            return next;
        }       
    }

    private Node<E> head = null;
    private Node<E> tail = null;
    private int size = 0;

    public SinglyLinkedList()
    {

    }

    public int size()
    {
        return size;
    }

    public boolean isEmpty()
    {
        return size == 0;
    }

    public void addFirst(E e)
    {
        head = new Node<>(e, head);

        if (size == 0)
        {
            tail = head;
        }
        size++;
    }

    public E removeFirst()
    {
        if (isEmpty())
        {
            return null;
        }
        E answer = head.getElement();
        head = head.getNext();
        size--;

        if (size == 0)
        {
            tail = null;
        }
        return answer;
    }
}

Here is my final SinglyLinkedListTest class:

package PostFix;
import java.util.Scanner;

public class SinglyLinkedListTest 
{
    public static void main(String[] args)
    {
        Double num1, num2, answer;
        char c;

        Stack<Double> stack = new LinkedStack<>();
        Scanner input = new Scanner(System.in);

        System.out.println("Enter the expression you would like to evaluate: ");
        String someString = input.nextLine();

        for (int index = 0; index < someString.length(); index++)
        {
            c = someString.charAt(index);

            if (Character.isDigit(c))
            {
                stack.push((double)Character.digit(c, 10));
            }
            else if (c == '+')
            {
                num2 = stack.pop();
                num1 = stack.pop();
                answer = num1+num2;
                stack.push(answer);
            }
            else if (c == '-')
            {
                num2 = stack.pop();
                num1 = stack.pop();
                answer = num1-num2;
                stack.push(answer);
            }
            else if (c == '*')
            {
                num2 = stack.pop();
                num1 = stack.pop();
                answer = num1*num2;
                stack.push(answer);
            }
            else if (c == '/')
            {
                num2 = stack.pop();
                num1 = stack.pop();
                answer = num1/num2;
                stack.push(answer);
            }     
        }
        System.out.println("The result is: " + stack.pop());
    }
}

Answer 1

Stack<String> buffer = new LinkedStack<>();

• Poor name: call it stack.

• You've declared it as Stack<String> but you're pushing chars:

   buffer.push(someString.charAt(index));
  

  and Objects:

  buffer.push(answer);
  

  and popping ints:

  num1 = buffer.pop();
  

• You are never either pushing or popping strings.

Just make up your mind. You should be pushing and popping ints, or longs, or doubles, or BigDecimals, depending on what precision you need.

EDIT

buffer.push((double)c);

is invalid. You're pushing the ASCII value, not the numeric value it corresponds to. You need

buffer.push((double)Character.digit(c, 10));

You also need an else after each if block: if the character is a digit, it won't be a +, and if it's a + it won't be a -, etc.