Data Structures and Algorithms - Applications of stacks (binary conversion, bracket matching)

Application of the stack

PS: There are many applications that are simple to implement with a stack, such as binary conversion, bracket matching, etc. Learn computer know, 2 decimal, 8 decimal, 10 decimal, hexadecimal, etc., the conversion between decimal is also need to master, in case of emergency, so we can write a piece of their own program if you can android, you can directly pack into APK. Here's a little bit of C code to follow these two applications.

  • conversion in progression
  • bracket matching

1: Binary conversion

  Want to make one yourself conversion in progression tools, First we need to know how to implement the conversion between binary, What we normally use is10 binary, If you want to convert to8 What about the progressive system?, Follow the method, as shown

As you can see,N It's us. importation of10 integer, divided by8, The remainder is retained on the stack, recipient168 Then with8 integer division operation, untilN div 8 tantamount to0, Finally, just take the data out of the stack, It just so happens that the rules of the stack are used, First-in, last-out feature。

1.1: Define the stack structure

typedef struct zhan{
    int data;
    struct zhan *next;

1.2: Initializing the stack

 *  Initializing the stack
 * */
ZhanL initZhan(){
    ZhanL L =(ZhanL)malloc(sizeof(zhan));
    return L;

1.3 in-stack and out-stack operations

In the pop method, assigning L to s is mainly to release the free stack bits after exiting the stack, and the push method uses the tail insertion method.

  * stack-in operation
 * */
int push(ZhanL &L,int data){
     // Create a new node
    ZhanL p=(ZhanL)malloc(sizeof(zhan));
    p->next = L;
    L = p;
    return 0;
int pop(ZhanL &L){
         ZhanL s=L;//free space for
        printf("%d ",s->data);
        L = L->next;
//            printf(" stack top (computing)%d 
        } else{
            printf(" warehouse
    return 0;

1.4:Conversion method

 * Conversion method
 * */
 int zhuanhuan(ZhanL &L,int data,int jz){
     while (data){
         data = data/jz;

     while (L){
    return 0;

1.5: Use

int main(){
    ZhanL L;
    printf(" invite importation A decimal number");
    int data,jz;
    printf(" invite importation Converted binary");
    return 0;

Results graph.

2: Bracket matching

What is it? bracket matching?

When writing code, two types of parentheses are often used: parentheses "()" and curly braces "{}" . Regardless of which brackets are used, one of the most important factors for a program to compile without problems is whether the brackets used match the . When writing a program, parentheses can be nested, i.e.: "({()})" of this form, but "({)" or "({}" do not fit the bill.


We can enter characters from the keyboard, separated by spaces, in if it is the left bracket ( { ), it goes on the stack, if it is the right bracket ( } ) it goes out of the stack for comparison to see if a pair of brackets is entered, if it matches, the next comparison is made, otherwise RETURN, there is no need for further comparison. Since there are stacks in and stacks out above, we won't give them here, just use the above.

Note: Change the int type in the structure above, to a char type.

2.1: bracket matching algorithm

Normal from the console importation, space separating, meetm close, (located) at importation during, Left bracket detected, push on, The right bracket has to be compared with the left bracket, How does it compare?, We can flip the right bracket, To put it plainly, when you meet a right bracket, you make it take the specified left bracket form, as if:if(ch == '}') This is the time to putch turn into (sth. else) { And then compare it with the elements in the stack。

int main(){
    ZhanLink zhanLink;
    zhanLink = initLink();
    char ch;
    while(ch != 'm'){
        scanf(" importation%c  ",&ch);
        ch = getchar();
        switch (ch){
            case '{':
            case '(':
            case '}':
            case ')':
//                printf("      %c
                char e=pop(zhanLink);

                if(ch == '}'){
                }else if(ch == ')'){
                    ch = '(';
//                printf(" after modification%c
                if(e == ch){
                    if(ch == '{'){
                    }else if(ch == '('){
                        ch = ')';
                    printf(" match%c %c
                    printf(" brackets do not match
                    return 0;
    printf(" Reasonable match");

//    pop(zhanLink);

    return 0;

1、Shenzhen aggregated trading system development blockchain technology developer
2、Jedi are coming out with a new mode to retain players yet such a mode is being trolled
3、How blockchain is changing the worlds financial landscape
4、Ethernet Food Traceability Case
5、Digital Source Technology driverless concept stocks have strengthened today Digital Source Technology strong

    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送