Can someone help me with this algorithm please! th

kishan4910 · January 16th, 2008, 04:52 PM

Hi, i've been trying to do this algorithm problem recently but i cant seem to beable to follow the algorithm, It requires me to fill in a table which i can partly complete but dont seem to beable to understand some lines like when i have to push anAarray, could some please help me by seeing what the answers is so i can check if im right or not and could some please translate the algorithm so it is easier to understand so i can trace it properly, any help will be appreciated, thanks!

The procedure PUSH(anArray, top, ch) first adds one to the value of top and then stores the single
character held in ch in the one-dimensional array anArray at anArray[top].

The function POP(anArray, top) returns the character held in anArray[top] and then takes 1 off the
value of top.

The function NEXTCHAR(str) returns the next character in its argument str which is a string.

The functions F(ch), G(ch) and R(ch) take a single character as input and return a value according to the table below.

http://www.imagehosting.com/out.php/...9_untitled.bmp

In the algorithm, & joins two strings together (concatenation).

Code:

1. INPUT aString
2. aString = aString & '')''
3. top = 0
4. PUSH(anArray, top, ''('')
5. newString = '' ''
6. rank = 0
7. current = NEXTCHAR(aString)
8. WHILE current <> '' ''
9. IF top < 1 THEN
10. OUTPUT ''Invalid string''
11. END the procedure
12. ENDIF
13. WHILE F(current) < G(anArray[top])
14. temp = POP(anArray, top)
15. newString = newString & temp
16. rank = rank + R(temp)
17. IF rank < 1 THEN
18. OUTPUT ''Invalid string''
19. END the procedure
20. ENDIF
21. ENDWHILE
22. IF F(current) <> G(anArray[top]) THEN
23. PUSH(anArray, top, current)
24. ELSE
25. POP(anArray, top)
26. ENDIF
27. current = NEXTCHAR(aString)
28. ENDWHILE
29. IF top <> 0 OR rank <> 1 THEN
30. OUTPUT ''Invalid string''
31. ELSE
32. OUTPUT ''Valid string''
33. ENDIF
34. END of procedure

I have to fill in the table below three times by using the three different input strings which are:
CD
p*(q
(v-w)*(x+y)

http://www.imagehosting.com/out.php/..._untitled2.bmp[/URL]

you have to work left to write in the table filling it in everytime something changes,

Ive been able to fill in "cd" table which i think is mostly right but im having problem with the other two. its harder then its seems lol. If someone could translate it so its easier to understand, i would be very gratefull. thanks for your help!!

BrianWren · January 16th, 2008, 05:30 PM

Code:

    Function MyFunc(ByVal aString As String) As String

2.      aString = aString  & ")"
3.      Dim top As Integer  ' Defaults to zero

4.      PUSH(anArray, top, "(")

5.      Dim newString As String
            newString = " "

6.      Dim rank As Integer  ' Defaults to zero

        Dim temp    As String * 1
7.      Dim current As String * 1
            current = NEXTCHAR(aString)

8.      While current <> " "
9.          If top < 1 Then
10.             MyFunc = "Invalid string"
11.             Exit Function
12.         End If

13.         While F(current) < G(anArray[top])  ' I don't see where
                                                ' anArray comes from...
14.             temp = POP(anArray, top)
15.             newString = newString & temp
16.             rank = rank + R(temp)

17.             If rank < 1 Then
18.                 MyFunc = "Invalid string"
19.                 Exit Function
20.             End If

21.         End While

22.         If F(current) <> G(anArray[top]) Then
23.             PUSH(anArray, top, current)
24.         Else
25.             POP(anArray, top)
26.         EndIf

27.         current = NEXTCHAR(aString)

28.     End While

29.     If top <> 0 OR rank <> 1 Then
30.         MyFunc = "Invalid string"
31.     Else
32.         MyFunc = "Valid string"
33.     End If

34. End Function

Perhaps this will help you wade through the algorithm.

kishan4910 · January 16th, 2008, 06:05 PM

Nope, is it possible to translate it to a more understandable version so i know what im doing at each line of the algorithm?

gbianchi · January 16th, 2008, 08:26 PM

well.. we don't do homework ;)

wich line don't you understand?? maybe the best you can do is take the great job that Brian do and add a coment before each lines that tells you what is does...
I think that the desirable here is that you can understand how an algorith work.. in fact you are dealing with a stack.

HTH

Gonzalo

================================================== =========
Read this if you want to know how to get a correct reply for your question:
http://www.catb.org/~esr/faqs/smart-questions.html
^^Took that from dparsons signature and he Took that from planoie's profile
================================================== =========
My programs achieved a new certification (can you say the same?):
WORKS ON MY MACHINE
http://www.codinghorror.com/blog/archives/000818.html
================================================== =========
I know that CVS was evil, and now i got the proof:
http://worsethanfailure.com/Articles...-Hate-You.aspx
================================================== =========

kishan4910 · January 17th, 2008, 05:04 AM

Its not homework, and i dont understand the push function and what to do when i enter the while loop from line 13.

gbianchi · January 17th, 2008, 07:58 AM

MMM.. ok...

push put a char in the array at position top... probably push and pop also add or decrease top by 1 (push +1, pop -1)... If that is not true (you never stated that) then your case is solved before start because it will never pass line 9 in any case... (if top < 1 will always be true)...

then the while line compares 2 chars, the input of function f and g.. since you have the 2 inputs the only thing you have to do is look into the table to see what are the results...

and I will never believe that this is not homework ;)

HTH

Gonzalo

================================================== =========
Read this if you want to know how to get a correct reply for your question:
http://www.catb.org/~esr/faqs/smart-questions.html
^^Took that from dparsons signature and he Took that from planoie's profile
================================================== =========
My programs achieved a new certification (can you say the same?):
WORKS ON MY MACHINE
http://www.codinghorror.com/blog/archives/000818.html
================================================== =========
I know that CVS was evil, and now i got the proof:
http://worsethanfailure.com/Articles...-Hate-You.aspx
================================================== =========

kishan4910 · January 17th, 2008, 09:02 AM

really, it aint homework, And this algorithm does work as my friend has completed it and has the correct answer, i just dont know how he did it, i managed to get a answer when i input "cd" but it dosent look right, shall i post the table on here so you can check? ive also got an example but i cant figure out how the algortihm works from the example either.

gbianchi · January 17th, 2008, 09:09 AM

well.. did you understand what I wrote before??

what about the pop and push function.. do they do something to top???

HTH

Gonzalo

================================================== =========
Read this if you want to know how to get a correct reply for your question:
http://www.catb.org/~esr/faqs/smart-questions.html
^^Took that from dparsons signature and he Took that from planoie's profile
================================================== =========
My programs achieved a new certification (can you say the same?):
WORKS ON MY MACHINE
http://www.codinghorror.com/blog/archives/000818.html
================================================== =========
I know that CVS was evil, and now i got the proof:
http://worsethanfailure.com/Articles...-Hate-You.aspx
================================================== =========

kishan4910 · January 17th, 2008, 10:24 AM

Well i know push adds one interger on to top and pop takes one integer off top, Top relate to array indexing i think. array indexing in this algorithm starts at 1.

gbianchi · January 17th, 2008, 10:34 AM

You never stated that ;)..

well.. did you understand now how pop and push works?

HTH

Gonzalo

================================================== =========
Read this if you want to know how to get a correct reply for your question:
http://www.catb.org/~esr/faqs/smart-questions.html
^^Took that from dparsons signature and he Took that from planoie's profile
================================================== =========
My programs achieved a new certification (can you say the same?):
WORKS ON MY MACHINE
http://www.codinghorror.com/blog/archives/000818.html
================================================== =========
I know that CVS was evil, and now i got the proof:
http://worsethanfailure.com/Articles...-Hate-You.aspx
================================================== =========