使用单链表评估后缀表达式

Question

我正在编写一个程序，要求用户输入后缀表达式，然后将结果输出到表达式。我正在尝试使用单链表并使用适配器模式创建堆栈来执行此操作。

SinglyLinkedList class、LinkedStack class 和 Stack 实现的代码都直接来自一本数据结构书我拥有。所以 SinglyLinkedListTest class 是唯一一个有我自己的代码的（并且有错误）。

我以前写过一个简单地使用堆栈计算后缀表达式的程序，但这次我对包含的额外 classes 感到困惑。

我确定我有很多错误，但对我来说最明显的错误是在我的 SinglyLinkedListTest class 中，每次我将一个值压入堆栈时。我知道问题是我试图将对象和字符压入堆栈，而不是将匹配 push(E e) 的参数压入堆栈，但我不知道如何更改我的代码以使其工作。

如有任何建议或意见，我们将不胜感激。

这是我的堆栈实现：

package PostFix;

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

    boolean isEmpty();

    void push(E e);

    E pop();
}

这是我的 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();
    }
}

这是我的单链表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;
    }
}

这是我的 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<>();

可怜的名字：叫它stack。

您已将其声明为 Stack<String> 但您正在推动 chars:

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

和Objects：

buffer.push(answer);

并弹出 ints:

num1 = buffer.pop();

你永远不会推动或弹出字符串。

你拿定主意吧。您应该推入和弹出 ints，或 longs，或 doubles，或 BigDecimals，具体取决于您需要的精度。

编辑

buffer.push((double)c);

无效。您推的是 ASCII 值，而不是它对应的数值。你需要

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

每个 if 块后还需要一个 else：如果字符是数字，则不会是 +，如果是 + 不会是-，等等

使用单链表评估后缀表达式

Evaluate a Postfix Expression Using a Singly Linked List

java

stack

linked-list

postfix-notation