Solved

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

Posted on 2015-01-28
1
129 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

Best Practices: Disaster Recovery Testing

Besides backup, any IT division should have a disaster recovery plan. You will find a few tips below relating to the development of such a plan and to what issues one should pay special attention in the course of backup planning.

Question has a verified solution.

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

Suggested Solutions

Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
Dependencies in Software Design In software development, the idea of dependencies (http://en.wikipedia.org/wiki/Coupling_%28computer_programming%29) is an issue of some importance. This article seeks to explain what dependencies are and where they …
This Micro Tutorial will give you a basic overview how to record your screen with Microsoft Expression Encoder. This program is still free and open for the public to download. This will be demonstrated using Microsoft Expression Encoder 4.
This video shows how to use Hyena, from SystemTools Software, to bulk import 100 user accounts from an external text file. View in 1080p for best video quality.

770 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