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

Posted on 2015-01-28
Medium Priority
Last Modified: 2015-02-01
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.
Question by:engiLAB
1 Comment
LVL 23

Accepted Solution

ambience earned 2000 total points
ID: 40577059
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):
        push V on H
        push V on stack
  if hashsize equals size of H: // Nothing got calculated!!!
    throw CycleException
  if stack is empty:
    print DONE!
  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


Featured Post

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

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.

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

Article by: Nadia
Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
This is an update to some code that someone else posted on Experts Exchange. It is an alternate approach, I think a little easier to use, & makes sure that things like the Task Bar will update.
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
To export Lotus Notes to Outlook PST or Exchange and Domino Server files to Exchange Server or PST files with ease, go for Kernel for Lotus Notes to Outlook conversion tool. Through the video, you can watch the conversion process. A common user with…

586 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question