栈的四则运算

中缀转后缀的数组&&直接输出

#include < stdio.h>
#include < stdlib.h>
#include< string.h>
#include < stdbool.h> // 包含bool函数
#define MAXSIZE 1000
typedef char ElementType;
typedef struct DStack* Stack;
struct DStack
{
    int Top;
    ElementType Data[MAXSIZE];//用数组的顺序堆栈
} S; //Top初始化问题
bool Priority(char a, char b)
{
    // b==* or /
    //if a>b return true
    if (a == '*'||a=='/')
        return true;
    else
        return false;
}
//转换成中缀并且输出
void Change(ElementType* str, Stack p)
{
    int i = 0;
    p = (Stack)malloc(sizeof(int) + sizeof(ElementType) * MAXSIZE);
    //结构体定义时候并没有为他分配空间只是告诉系统如何表示数据
    p->Top = -1;
    while (str[i] != '#')
    {
        if (str[i] == 32)
            continue;
        if (str[i] >= '0' && str[i] <= '9')
            printf("%c", str[i]);
        else if (str[i] == '(')
            p->Data[++p->Top] = '(';
        else if (str[i] == ')')
        {
            while (p->Data[p->Top] != '(')
                printf("%c", p->Data[p->Top--]);
            p->Top--;
        }
        else if (str[i] == '+' || str[i] == '-')
        {
            while (p->Top != -1 && p->Data[p->Top] != '(') //短路原理p->Top!=-1一定要写在前面
                printf("%c", p->Data[p->Top--]);
            p->Data[++p->Top] = str[i]; //push after pop
        }
        else //  * or /
        {
            while (p->Top != -1 && Priority(p->Data[p->Top], str[i]))
                printf("%c", p->Data[p->Top--]);
            p->Data[++p->Top] = str[i];
        }
        i++;
    }
    while (p->Top != -1)
        printf("%c", p->Data[p->Top--]);
}
int main()
{
    ElementType str[10000];
    gets(str);
    Stack p=NULL;
    Change(str, p);
    return 0;
}

个位数的四则运算完整

#include < stdio.h>
#include < stdlib.h>
#include < string.h>
#include < stdbool.h> // 包含bool函数
#define MAXSIZE 1000
#define LEN (sizeof(int) + sizeof(ElementType) * MAXSIZE) //直接宏定义
typedef char ElementType;
typedef struct DStack *Stack;
struct DStack
{
    int Top;
    ElementType Data[MAXSIZE]; //用数组的顺序堆栈
} S;                           //Top初始化问题
bool Priority(char a, char b)
{
    // b==* or /
    //if a>b return true
    if (a == '*' || a == '/')
        return true;
    else
        return false;
}
//转换成中缀并且输出
void Change(ElementType *str, Stack p, int *Size, ElementType strs[])
{
    int i = 0;
    p = (Stack)malloc(LEN);
    //结构体定义时候并没有为他分配空间只是告诉系统如何表示数据
    p->Top = -1;
    while (str[i] != '#')
    {
        if (str[i] == 32)
            continue;
        if (str[i] >= '0' && str[i] <= '9')
            //printf("%c", str[i]);
            strs[(*Size)++] = str[i];
        else if (str[i] == '(')
            p->Data[++p->Top] = '(';
        else if (str[i] == ')')
        {
            while (p->Data[p->Top] != '(')
                //printf("%c", p->Data[p->Top--]);
                strs[(*Size)++] = p->Data[p->Top--];
            p->Top--;
        }
        else if (str[i] == '+' || str[i] == '-')
        {
            while (p->Top != -1 && p->Data[p->Top] != '(') //短路原理p->Top!=-1一定要写在前面
                strs[(*Size)++] = p->Data[p->Top--];
            p->Data[++p->Top] = str[i]; //push after pop
        }
        else //  * or /
        {
            while (p->Top != -1 && Priority(p->Data[p->Top], str[i]))
                strs[(*Size)++] = p->Data[p->Top--];
            p->Data[++p->Top] = str[i];
        }
        i++;
    }
    while (p->Top != -1)
        strs[(*Size)++] = p->Data[p->Top--];
    strs[*Size] = '\0';
}
void Out(int Size, ElementType strs[]) 
//后缀表达式计算,只是个位数的乘法结果也必须是个位数
{
    int i = 0, temp = 0;
    Stack p = (Stack)malloc(LEN);
    p->Top = -1;
    while (i < Size)
    {
        if (strs[i] >= '0' && strs[i] <= '9')
            p->Data[++p->Top] = strs[i];
        else
        {
            switch (strs[i])
            {
            case '+':
                temp = p->Data[p->Top] + p->Data[p->Top - 1]-'0'-'0';
                break;
            case '-':
                temp = p->Data[p->Top] - p->Data[p->Top - 1];
                break;
            case '*':
                temp = (p->Data[p->Top]-'0') * (p->Data[p->Top - 1]-'0');
                break;
            case '/':
                temp = (p->Data[p->Top--]-'0') / (p->Data[p->Top - 1]-'0');
                break;
            }
            p->Top--;
            p->Data[p->Top] = temp+48;
        }
        i++;
    }
    printf("%d",p->Data[p->Top]-'0');
}
int main()
{
    ElementType str[10000], strs[10000];
    int Size = 0;
    gets(str);
    Stack p = NULL;
    Change(str, p, &Size, strs);
    printf("%s\n", strs);
    Out(Size,strs);
    return 0;
}

总结

中缀转后缀：
1.空栈直接压入
2.只有优先级比栈顶高的才可以压入，如果优先级比栈顶低或者等于，将栈顶一直弹出直到遇见左括号或者栈底
3.遇见右括号时，将栈一直弹出知道遇见左括号

个位数的四则运算：
1.从左往右遇见数字就Push，遇见字符就Pop出栈顶的头2数进行运算把结果再放入栈顶

Time

2020 4 14 22:36
go up!!! keep up!!!