# How to check for balanced parentheses with mod?

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;
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.

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.

• \bmod gives you better spacing for the binary operator than \mod does. – Brian M. Scott Mar 3 '12 at 5:18
• 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? – user93200 Mar 3 '12 at 23:12
• 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$. – sdcvvc Mar 3 '12 at 23:44
• Thank you for a clear explanation. – user93200 Mar 4 '12 at 1:08