Solved

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

Posted on 2015-01-28
1
132 Views
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.
0
Comment
Question by:engiLAB
1 Comment
 
LVL 22

Accepted Solution

by:
ambience earned 500 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):
        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

Featured Post

Active Directory Webinar

We all know we need to protect and secure our privileges, but where to start? Join Experts Exchange and ManageEngine on Tuesday, April 11, 2017 10:00 AM PDT to learn how to track and secure privileged users in Active Directory.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
update joined tables 2 55
how to make 2 step back? ..\..\ ExtractFilePath (paramstr(0)) 5 52
Delphi Seattle StructureView color 1 14
AvlTree-Node Data type 4 14
Article by: Nadia
Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
Introduction This question got me thinking... (http://www.experts-exchange.com/questions/28707487/GLOBALS.html) Why shouldn't we use Globals? This is a simple question without a simple answer.  How do you explain these concepts to a programmer w…
In a recent question (https://www.experts-exchange.com/questions/29004105/Run-AutoHotkey-script-directly-from-Notepad.html) here at Experts Exchange, a member asked how to run an AutoHotkey script (.AHK) directly from Notepad++ (aka NPP). This video…
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…

830 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