Solve polynomial equation using Linked List

Question

I am trying to write a Java program that takes an arithmetic expression, converts it from Infix to Postfix and evaluates the answer. However, I need to represent the expressions as Polynomials with the help of Linked Lists and perform Postfix evaluation on them. I have completed the Infix to Postfix conversion and know how to evaluate Postfix. But I am struggling to represent the polynomial expression using Linked List.

For example, if the Postfix expression is: 40 50 -

I need to store 40 as 4*10^1 + 0*10^1 in a Linked List. It can be done by having 2 nodes, Coefficient and Exponent, in the Linked List. Same thing for 50.

The problem is, I don't know how many linked lists I'll need for any given expression. If the postfix expression is 40 50 60 - + then I need to store all 3 numbers in separate lists and store them in a stack till I find an operator. Can anyone please give me any suggestions on how to proceed?

Answer 1

You don't need to store the exponent in the linked list: the exponent can be given by the digit's position. For example 365 can be stored as the list 5->6->3, though storing a single digit per list node is not so efficient.

You will need as many linked lists as there are input numbers, and you won't know how many there will be before reading the expression will you?