#imagine-eval

1 messages · Page 1 of 1 (latest)

obtuse finch
#

stuff

#

Ok @serene creek

serene creek
#

Sus

obtuse finch
#

Alright

#

So you have a linked list of the tokens

#

You create a map

#

ops = {} or something

#

Then you iterate over all your tokens

# 
for token in tokens:
  if not token.isOperator():
    continue
  if ops[token.getPriority()] == None:
    ops[token.getPriority()] = []
  ops[token.getPriority()].add(token)```
#

Does this make sense

serene creek
#

yes

obtuse finch
#

You construct a map mapping each operator priority to a list of operators with that priority in the order they appear

serene creek
#

couldve just said that but i love that youre exercosing your python

obtuse finch
#

I know python, I just don't like it

#

Anyways

#

Once you have this map

#

You iterate top down

#

Start at the highest priority

serene creek
#

Ok

obtuse finch
#

So if your highest priority is 10

#

I mean, I guess you could do like

# 
keys = [i for i in ops.keys()]
keys.sort(reverse = True)```
#

This way it sorts in descending order

#

And you can iterate down the keys

#

Do you follow?

serene creek
#

Youre tryna assert dominance over me in python knowledge

obtuse finch
#

I'm not

#

I'm trying to show specific code for how you could do it

serene creek
#

yah im followin

obtuse finch
#

Alright

#

Now, once you have the keys sorted

#

Ah I forgot something

#

You need the linked list nodes, not the tokens themselves

#

One sec

serene creek
#

I got it

#

nah i got it

obtuse finch
#

Alright

#

So you understand what I mean by the linked list nodes, right?

serene creek
#

l, root, r

obtuse finch
#

And you understand why we are storing them instead of the tokens?

serene creek
#

while tokens:
l = tokens.get
op = tokens.get
r = tokens.get

#

@obtuse finch yes

obtuse finch
#

Okay

#

So now that we have them in a map

#

You iterate down the keys, and for each key, you get all of the linked list nodes for tokens that have that priority

#

Example:

# 
3 * 2 + 1```
# 
[3, *, 2, +, 1]```
#

Your map would look like this

# 
{
5: [*]
2: [+]
}```
#

Assuming * has priority 5 and + has priority 2

serene creek
#

? wait

#

holdup

obtuse finch
#

Ok

serene creek
#

L, Op, R
2 * 3

how do I do this without the value before

#

like

#

1 + 2 * 3

obtuse finch
#

You mean the linked list node?

serene creek
#

ye

#

its missing either r or l

obtuse finch
#

So for example the 1 in there

serene creek
#

ye

obtuse finch
#

Its prev pointer would be None

#

Since it's the head of the linked list

#

Likewise, the tail of the linked list has None as its next pointer

#

I gave you this example linked list implementation

#

You can copy it and translate it to python if you want

#

The only reason I had to do this is because java does not expose the linked list nodes in its implementation, but you need them

serene creek
#

so confused

#

do I need the tokens or the previous node

obtuse finch
#

You need the linked list node

#

Every linked list node has a pointer to the previous node and a pointer to the next node

serene creek
#
  • Node -
    prev_node
    root_token
    next_node
#

right?

obtuse finch
#

Root?

#

Why would each node need to store the root

#

It stores the previous token, the next token, and the data

#

The data in this case is a token

serene creek
obtuse finch
#

Ah

serene creek
#

isnt it called the root value

obtuse finch
#

I dunno

#

I've never heard it called root

#

Just data

serene creek
#

wait

#

I think I understand noe

obtuse finch
#

Right

#

So the advantage of a linked list is that you can remove adjacent tokens in O(1)

#

Constant time

#

It's super easy to do this

#

You just set the node's prev node to the prev node's prev

#

So, self.prev = self.prev.prev

#

You also need to then do self.prev.next = self

#

But yeah it's literally just 2 lines

serene creek
#

[1 + 2 * 3]
*: 6
+: 1

7

#

i know what a linked list is

obtuse finch
#

Whereas to remove from an array-backed list, it's O(n) because it has to shuffle all of the the elements forward/back to fill in the space

#

Alright

#

So you have your linked list

#

You have your map of priorities to the linked list nodes containing operators of that priority

#

You iterate down the priorities, getting each of these lists

#

For each operator node, you can evaluate it easily

#

You get the previous node and its token

#

You get the next node and its token

#

They should both be numbers

#

You evaluate that one operation, like 1 + 1 or something

#

Then you replace the value of the node with the result of that operation

#

So 1, +, 1 becomes 1, 2, 1

#

Then you use the linked list properties to remove the previous and next nodes

#

So it's just 2 now

#

This value can now be used in other operations

#

So if you continue and evaluate all the operators in order, if the expression is valid then the entire thing will become a single number by the end