Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
1  
\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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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