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.

$\endgroup$
5
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.