1
$\begingroup$

Using a single double and different int's for various types of parentheses, without stack how to check for balanced parentheses with mod? E.g.,

in: {[(a])c}; reads only parenthetical chars, uses double stack=0 as          stack emulator;   int correspondence: []: 4; {}: 5; (): 3;   read each char,       if opening parenthesis, push (i.e., use corresponding int value to           alter stack: I'm not sure how exactly, could be simply by adding           its value);       if closing, pop (i.e., use % to determine last pushed parenthetical          type, and if it matches, do something like subtract its value          from stack).   if stack==0 out: balanced. 

Somebody showed this, but I'm not clear on details.

1 Answers 1

5

Normally you would use a stack, scan the string and on opening bracket you push it, on closing bracket you check if it matches the top and pop.

To simulate a stack that has a finite alphabet, say $($, $[$ and $\{$ you can store it as an integer. I suggest you assign numbers $(=0$, $[=1$, $\{=2$. A stack will be stored with leading 1 in base 3. For example, $\{[([($ with $($ on top will be stored as $121010$.

To check if stack is empty, compare $x$ with 1.

To get topmost element, compute $x \bmod 3$.

To pop, divide $x$ by $3$ discarding remainder.

To push $n$ ($n=0,1,2$), replace $x$ by $3x+n$.

Of course you can replace $3$ if the stack can hold other types of brackets.

  • 0
    Thank you for a clear explanation.2012-03-04