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.

  • 1
    \bmod gives you better spacing for the binary operator than \mod does.2012-03-03
  • 0
    What is the limit on the depth of the stack if it is represented in this way? Can this be improved? How does \bmod give better spacing for the binary operator than \mod?2012-03-03
  • 0
    user93200: That would be about floor of $\log_3 2^{\text{width}-1}=O(\text{width})$, storing a stack of $n$ items requires a number of size up to $3^n$. Since you need to remember at least as many bits as the size of the stack, there is little chance of optimization (you could gain an extra bit with the leading 1, but not much more). On \bmod and \mod, it was a LaTeX issue, compare $n \mod 3$ and $n \bmod 3$.2012-03-03
  • 0
    Thank you for a clear explanation.2012-03-04