This is all about recursive problems and the part 1 of this assignment is warm up problems.

There are two warm up problems, one is Balancing parentheses and the second is Evaluating expressions, so lets start with the Balancing parentheses.

**Balancing parentheses**

To make sure that a there is opening and closing brackets within a string, the three brackets that we need to search for is {}, () and [] and if they are present in the string basically remove them and then recheck the string until it reaches “” (a empty state). If there is a non empty state of the string then return false, which means that the string is not balanced, here is a example taken from the assignment PDF file,

For example, the string “[(){}]” is shown to be balanced by the following chain of calls:

IsBalanced(“[(){}]”)

IsBalanced(“[{}]”)

IsBalanced(“[]”)

IsBalanced(“”) true

and here is the recursive code that I did come up with, the start is the empty string (str.size() == 0), else it tries to find the any one of the three strings in a for loop (breaks from the for loop if found) and if one is found then recall the IsBalanced function.

bool IsBalanced(string str) { int strPos=-1; if (str.size() == 0) return true; string findStr[] = {"()", "[]", "{}"}; for (int i =0; i < 3; i++) { strPos = str.find(findStr[i]); if (strPos >=0) break; } if (strPos >=0) return IsBalanced(str.substr(0, strPos) + str.substr(strPos+2)); return false; } |

**Evaluating expressions**

Evaluating expressions is when you have a mathematical equation that you need to equate, so for example as taken from the PDF assignment file

EvalInfixExp(“3”) = 3

EvalInfixExp(“(4 + 8)”) = 12

EvalInfixExp(“(25 – (2 * 10))”) = 5

Where the EvalInfixExp is the function that we call recursive, the way that I thought about this is that if there is no spaces then return the value (e.g. base case) and if there is no brackets in the string then it must be a maths query, which get the two values and the mathematical function (/,+,-,*) and equate them returning that value, but then if there is a “(” at the start, since all equations are valid, then equate inside that ( .. ) brackets, but if there is any ( … ) inside that main ( … ) then figure them out first, which is why I using the first_last_of “(” function to find the the end ( .. ) to equate and then the associated “)”, which in turn we just need to recall the function EvalInfixExp to figure out the value inside the string.

To think about it, what is happening is that is works from the inside to the out finding the values of the ( .. ) to reinsert them back into the string (the result of them that is), so in the end all we do is equate the last mathematical equation.

Here is the cpp recursive function.

int EvalInfixExp(string expString) { // so if the first character is ( then do else do other int brackPos1, brackPos2, returnValue =0; // try and find the outter () if (expString[0] == '(') { brackPos1 = expString.find_last_of("("); brackPos2 = expString.find_first_of(")", brackPos1); // find the value within the () and replace with the new value if (brackPos1 >= 0 && brackPos2 >=0) { brackPos1++; returnValue = EvalInfixExp(expString.substr(brackPos1, brackPos2 - brackPos1)); // need to replace the () with the value brackPos1--; expString.replace(brackPos1, brackPos2 - (brackPos1-1), IntegerToString(returnValue)); } return EvalInfixExp(expString); } else { // find out the actual value of the maths function if (expString.find_first_of(" ") < 0 || expString.find_first_of(" ") > expString.size()) return StringToInteger(expString); Scanner theExpScanner; theExpScanner.setInput(expString); theExpScanner.setSpaceOption(theExpScanner.IgnoreSpaces); int firstValue = StringToInteger(theExpScanner.nextToken()); string op = theExpScanner.nextToken(); string last; while (theExpScanner.hasMoreTokens()) last += theExpScanner.nextToken(); int secondValue = StringToInteger(last); if (op == "+") returnValue = firstValue + secondValue; if (op == "-") returnValue = firstValue - secondValue; if (op == "*") returnValue = firstValue * secondValue; if (op == "/") returnValue = firstValue / secondValue; return returnValue; } } |

I have attached the full source code and also the PDF assignment code.

Hi,

I am trying to solve the Problem of ListMnemonics recursively.

So the Problem being this.

Given a particular number say 637-8687 (NERVOUS) would be the word.

So for the older keypad’s seen on telephone’s I would have to create Mnemonics.

So for doing this, the first part being list out all the Permutations possible for a particular number series.

Ex: ListMnemonics(“723”) would result in

PAD PBD PCD QAD QBD QCD RAD RBD RCD SAD SBD SCD

PAE PBE PCE QAE QBE QCE RAE RBE RCE SAE SBE SCE

PAF PBF PCF QAF QBF QCF RAF RBF RCF SAF SBF SCF

For this my logic is

for the above number 723, somehow create all the permutations for 23 and then append for each of those permutations the letters of 7. That would give all the permutations possible for 723. The base case being if there is a single number then I would print its letters.

But I am having great difficulty accomplishing this.

If you dont mind can you please please provide code for this problem

Thank you so much.

Regards

Prashanth

Hi Prashanth,

This does sound like a interesting problem and I shall have a go at solving this for you, on the outset I would start with the first letter(s) from the number and create a stack of possible outputs and then add onto that the second letter onto the stack (if the first and second letter are a actual start of a word) which in turn will shorten the search if a 26 = BN is the search pattern then disregard because it may not be a word (have a words database if you can have one).

Or if you are just wanting to list out all of the possible outcomes, if you do the above without the word test then that will output all of the possible outcomes as well.

I shall have to take a look when I am abit more free (1-2 weeks :))

Hi Genux,

Unfortunately I could not get any further on that problem. Please let me know what you think of it.

Hi Prashanth,

Shall do, once I get some spare time I shall look into that problem, it does sound interesting in a recursive way :).