Solved

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

Posted on 2015-01-28
1
135 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
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

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20. The divisors of 12 are 1, 2, 3, 4, 6, 12 The divisors of 20 are 1, 2, 4, 5, 10 20 The highest number among the c…
Introduction This article discusses the Chain of Responsibility pattern, explaining What it is;Why it is; andHow it is At the end of this article, I hope you will be able to describe the use and benefits of Chain of Responsibility.  Backgrou…
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…
Exchange organizations may use the Journaling Agent of the Transport Service to archive messages going through Exchange. However, if the Transport Service is integrated with some email content management application (such as an antispam), the admini…

732 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