中缀表达式转后缀表达式

阳光穿透心脏的1/2处 2023-10-09 12:50 48阅读 0赞

算法

遍历中缀表达式中的数字和符号：
        对于数字直接输出
        对于符号：
            左括号：进栈
            运算符号：与栈顶符号进行优先级比较
                若栈顶符号优先级低：此符号进栈
                    （默认栈顶若是左括号，左括号优先级最低）
                若栈顶符号优先级不低：栈顶符号弹出并输出，之后进栈
                右括号： 将栈顶符号弹出并输出，直到匹配左括号
    遍历结束：将栈中的所有符号弹出并输出

#ifndef LINKSTACK_H_INCLUDED
    #define LINKSTACK_H_INCLUDED
    
    #include <stdlib.h>
    #include <stdio.h>
    
    //链式栈的结点
    typedef struct LINKNODE {
        struct LINKNODE *next;
    }LinkNode;
    
    
    //链式栈
    typedef struct LINKSTACK {
        LinkNode head;
        int size;
    }LinkStack;
    
    //初始化函数
    LinkStack *Init_LinkStack();
    
    //入栈
    void Push_LinkStack(LinkStack *stack, LinkNode *data);
    
    //出栈
    void Pop_LinkStack(LinkStack *stack);
    
    //返回栈顶元素
    LinkNode* Top_LinkStack(LinkStack *stack);
    
    //返回栈元素的个数
    int Size_LinkStack(LinkStack *stack);
    
    //清空栈
    void Clear_LinkStack(LinkStack *stack);
    
    //销毁
    void FreeSpace_LinkStack(LinkStack *stack);
    
    
    #endif // LINKSTACK_H_INCLUDED

#include "LinkStack.h"
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    
    //初始化函数
    LinkStack *Init_LinkStack() {
        LinkStack *stack = (LinkStack *)malloc(sizeof(LinkStack));
        stack->head.next = NULL;
        stack->size = 0;
        return stack;
    }
    
    //入栈
    void Push_LinkStack(LinkStack *stack, LinkNode *data) {
        if(stack == NULL){
            return;
        }
        if(data == NULL){
            return;
        }
        data->next = stack->head.next;
        stack->head.next = data;
        stack->size++;
    }
    
    //出栈
    void Pop_LinkStack(LinkStack *stack) {
        if(stack == NULL){
            return;
        }
        if(stack->size == 0){
            return;
        }
    
        //第一个有效结点
        LinkNode *pNext = stack->head.next;
        stack->head.next = pNext->next;
        stack->size--;
    }
    
    //返回栈顶元素
    LinkNode* Top_LinkStack(LinkStack *stack) {
        if(stack == NULL){
            return NULL;
        }
        if(stack->size == 0){
            return NULL;
        }
        //返回头结点后面的第一个元素
        return stack->head.next;
    }
    
    //返回栈元素的个数
    int Size_LinkStack(LinkStack *stack) {
        if(stack == NULL){
            return 0;
        }
        return stack->size;
    }
    
    //清空栈
    void Clear_LinkStack(LinkStack *stack) {
        if(stack == NULL){
            return;
        }
        stack->head.next = NULL;
        stack->size = 0;
    }
    
    //销毁
    void FreeSpace_LinkStack(LinkStack *stack) {
        if(stack == NULL) {
            return;
        }
        free(stack);
    
    }

/*
     * main.c
     *
     *  Created on: 2019年8月14日
     *      Author: Administrator
     */
    
    
    #include <string.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include "LinkStack.h"
    
    //判断是否是数字
    int IsNumber(char c) {
        return c >= '0' && c <= '9';
    }
    
    void NumberOperate(char *p) {
        printf("%c", *p);
    }
    
    //判断是不是左括号
    int IsLeftBracket(char c){
        return c=='(';
    }
    int IsRightBracket(char c){
        return c==')';
    }
    
    //判断是不是运算符号
    int IsOperator(char c) {
        return c == '+' || c == '-' || c=='*' || c == '/';
    }
    
    //返回运算符号优先级
    int GetPriority(char c) {
        if(c == '*' || c == '/') {
            return 2;
        }
        if(c == '+' || c == '-') {
            return 1;
        }
    
        return 0;
    }
    
    数字操作
    //void NumberOperate (char *p) {
    //  printf('%c', *p);
    //}
    
    
    
    typedef struct MYCHAR {
        LinkNode Node;
        char *p;
    }MyChar;
    
    //创建MyChar
    MyChar *CreateMyChar(char *p) {
        MyChar *myChar = (MyChar *)malloc(sizeof(MyChar));
        myChar->p = p;
        return myChar;
    }
    
    
    
    //左括号的操作
    void LeftOperate(LinkStack *stack, char *p) {
        Push_LinkStack(stack, (LinkNode *)CreateMyChar(p));
    }
    
    void RightOperate(LinkStack *stack, char *p) {
        //先判断栈中有没有元素
        while(Size_LinkStack(stack) > 0){
            MyChar *mychar = (MyChar *)Top_LinkStack(stack);
            if(IsLeftBracket(*(mychar->p))){
                Pop_LinkStack(stack);
                break;
            }
            //输出
            printf("%c",*(mychar->p));
            //弹出
            Pop_LinkStack(stack);
            //释放内存
            free(mychar);
        }
    }
    
    //运算符号操作
    void OperatorOperate(LinkStack *stack, char *p) {
    
    
        //先取出栈顶符号
        MyChar *mychar = (MyChar *)Top_LinkStack(stack);
        if(mychar == NULL) {
            Push_LinkStack(stack, (LinkNode *)CreateMyChar(p));
            return;
        }
        //如果栈顶元素优先级低于当前字符的优先级， 直接入栈
        if(GetPriority(*(mychar->p)) < GetPriority(*p)) {
            Push_LinkStack(stack, (LinkNode *)CreateMyChar(p));
            return;
        }else {
            //如果栈顶符号优先级不低
            while(Size_LinkStack(stack) > 0) {
                MyChar *mychar2 = (MyChar *)Top_LinkStack(stack);
                //如果优先级低的 当前符号入栈
                if(GetPriority(*(mychar2->p)) < GetPriority(*p)) {
                    Push_LinkStack(stack, (LinkNode *)CreateMyChar(p));
                    break;
                }
                //输出
                printf("%c", *(mychar2->p));
                //弹出
                Pop_LinkStack(stack);
                //释放
                free(mychar2);
            }
        }
    }
    
    int main() {
        char *str = "8+(3-1)*5";
        printf("%s\n",str);
        char *p = str;
    
        //创建栈
        LinkStack *stack = Init_LinkStack();
    
        while (*p != '0'){
            //如果是数字
            if(IsNumber(*p)){
                NumberOperate(p);
            }
    
            //如果是左括号，直接进栈
            if(IsLeftBracket(*p)){
                LeftOperate(stack, p);
            }
    
            //如果是右括号
            if(IsRightBracket(*p)){
                RightOperate(stack, p);
            }
    
            if(IsOperator(*p)) {
                OperatorOperate(stack, p);
            }
            p++;
        }
    
        system("pause");
        return 0;
    }

输出结果

请按任意键继续. . . 
    
    8+(3-1)*5
    831-5*+1

转载于:https://www.cnblogs.com/wjw-blog/p/11355498.html