• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 158
  • Last Modified:

Methods to solve scripts with cell references (up/down dependancy and circular reference detection)

Dear Experts,

I´ve been developing a parser/interpreter in Delphi to solve scripts which use functions and variables located in cells (for the while only in lines and using one single column). I´m using this to create a list of input parameters and calculated parameters.

The parser is doing very well, but the approach to update values in the cells uses a top to bottom update. In this case, bottom cells can only use top variables.

Thinking about extending this list to more columns and to allow top cells to use bottom variables, which method (algorithm) could I use to correctly update all cells ? I am also not figuring how to detect circular reference out.

I´ll appreciate any help on this. Thanks.
0
engiLAB
Asked:
engiLAB
1 Solution
 
ambienceCommented:
One algorithm could be like this.

Q = queue of all variables
S = empty stack
H = empty hashtable

while stack is empty 
{
  hashsize = size of H
  while not queue is empty 
  {
      V = pop variable from list
      if canBeCalculated(V):
        calculateValue(V)
        push V on H
      else
        push V on stack
  }
  
  if hashsize equals size of H: // Nothing got calculated!!!
    throw CycleException
    
  if stack is empty:
    print DONE!
    return
    
  pop all from S into Q
}
       

function canBeCalculated(v)
{
  if V's expression is constant:
    return true
  if all dependent variables of V are in H:
    return true
}

Open in new window

0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now