逆波兰表达式

求表达式（1 - 2） * (4 + 5)的值

• 人类早就熟悉这种中缀表达式的计算公式，随便拉一个小朋友过来，他就直到这个结果是等于-9的，因为括号里面的要先进行计算。
• 但计算机不喜欢了，因为我们有小括号中括号大括号，还允许一个嵌套一个，这样子计算机就要进行很多次if判断才能决定那里先计算。

逆波兰表达式（后缀表达式）

波兰逻辑学家Jan.Lukasiewicz，发明了一种不需要括号的后缀表达式，我们通常把它称为波兰表达式（RPN）。

• 上面表达式（1 - 2） * (4 + 5) 的波兰表达式是这样的： 1 2 - 4 5 + *
• 这种表达式人类是不太好接受的，不过对计算机来说，利用栈的特点，就可以将这种后缀表达式的性能发挥到极致。

用栈来求解表达式（1 - 2） * (4 + 5)的值

• 数字1和2进栈，遇到减号运算符这弹出两个元素进行运算并把结果入栈。

图片.png

• 4和5入栈，遇到加号运算符，4和5弹出栈，相加后将结果9入栈。

图片.png

• 然后又遇到乘法运算符，将9和-1弹出栈进行乘法计算，此时栈空并无数据压栈，-9为最终运算结果。

图片.png

• 正常的表达式 --->逆波兰表达式
  a + b ---> a b +
  a + (b - c) ---> a b v - +
  a + (b - c) * d ---> a b c - d * +

*代码实现（c语言）

#include<stdafx.h>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<ctype.h>

#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10
#define MAXBUFFER 10

typedef double ElemType;
typedef struct {
    ElemType *base; //指向栈底的指针
    ElemType *top; //指向栈顶的指针
    int stackSize; //当前可使用的最大容量
}sqStack;

void InitStack(sqStack *s) {
    s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if (!s->base)
    {
        exit(0);
    }
    s->top = s->base;
    s->stackSize = STACK_INIT_SIZE;
}
//入栈操作要在栈顶进行，每次向栈中压入一个数据，top指针就要+1,直到栈满为止
void Push(sqStack *s, ElemType e) {
    if (s->top - s->base >= s->stackSize)
    {
        s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
        if (!s->base)
        {
            exit(0);
        }
    }
    *(s->top) = e;
    s->top++;
}
//出栈操作就是在栈顶取出数据，栈顶指针随之下移操作，每当从栈内弹出一个数据，栈的当前容量就-1
void Pop(sqStack *s, ElemType *e) {
    if (s->top == s->base)
    {
        return;
    }
    *e = *--(s->top);
}
//求栈的长度
int StackLen(sqStack s) {
    return s.top - s.base;
}

//清空栈， 将栈中的元素全部作废，但栈本身物理空间并不发生改变（不是销毁）
void ClearStack(sqStack *s) {
    s->top = s->base;
}
//销毁一个栈， 释放掉该栈所占据的物理内存空间
void DestoryStack(sqStack *s) {
    int i, len;
    len = s->stackSize;
    for (i = 0; i < len; i++)
    {
        free(s->base);
        s->base;
    }
    s->base = s->top = NULL;
    s->stackSize = 0;
}

int main() {
    sqStack s;
    char c;
    double d, e;
    char str[MAXBUFFER];
    int i = 0;

    InitStack(&s);
    printf("请按逆波兰表达式输入待计算的数据，数据与运算符之间用空格隔开，以#作为结束标志：");
    scanf_s("%c", &c);
    while (c != '#')
    {
        while (isdigit(c) || c == '.')
        {
            str[i++] = c;
            str[i] = '\0';


            if (i >= 10)
            {
                printf("出错，输入的单个数据过大!\n");
                return -1;
            }
            scanf_s("%c", &c);
            if (c == ' ')
            {
                d = atof(str);
                Push(&s, d);
                i = 0;
                break;
            }
        }


        switch (c)
        {
        case '+':
            Pop(&s, &e);
            Pop(&s, &d);
            printf("****%f***%f\n", e, d);
            Push(&s, d + e);
            break;
        case '-':
            Pop(&s, &e);
            Pop(&s, &d);
            Push(&s, d - e);
            break;
        case '*':
            Pop(&s, &e);
            Pop(&s, &d);
            Push(&s, d * e);
            break;
        case '/':
            Pop(&s, &e);
            Pop(&s, &d);
            if (e != 0)
            {
                Push(&s, d / e);
            }
            else
            {
                printf("\n出错：除数为0!\n");
            }
            break;
        default:
            break;
        }
        scanf_s("%c", &c);
    }
    Pop(&s, &d);
    printf("最终的计算结果是：%f", d);

    getchar();
    getchar();
    getchar();
    return 0;
}

中缀表达式转换成逆波兰表达式

人类喜欢这样的表达式：（1-2）*（4+5）
而不是这样的：1 2 - 4 5 + *

• 下面我们来动手写一个中缀表达式转换成后缀表达式的计算器：
  转换规则： 从左到右遍历中缀表达式的每个数字和符号，若是数字则直接输出，若是符号，则判断其与栈顶符号的优先级，是右括号或者优先级低于栈顶符号，则栈顶元素依次出栈并输出，直到遇到左括号或栈空才将其入栈。
• 代码实现

int main() {
    sqStack s;
    char c, e;
    InitStack(&s);
    printf("请输入中缀表达式，以#作为结束标志：");
    scanf_s("%c", &c);
    while (c != '#')
    {
        while (c >= '0' && c < '9')
        {
            printf("%c", c);
            scanf_s("%c", &c);
            if (c < '0' || c > '9')
            {
                printf(" ");
            }
        }

        if(')' == c)
        {
            Pop(&s, &e);
            while ('(' != e)
            {
                printf("%c", e);
                Pop(&s, &e);
            }
        }
        else if('+' == c || '-' == c)
        {
            if (!StackLen(s))
            {
                Push(&s, c);
            }
            else
            {
                do
                {
                    Pop(&s, &e);
                    if ('(' == e)
                    {
                        Push(&s, e);
                    }
                    else
                    {
                        printf("%c", e);
                    }
                } while (StackLen(s) && '(' != e);

                Push(&s, c);
            }
        }
        else if('*' == c || '/' == c || '(' == c)
        {
            Push(&s, c);
        }
        else if('#' == c)
        {
            break;
        }
        else
        {
            printf("\n出错，输入格式错误！\n");
            return -1;
        }
        scanf_s("%c", &c);
    }

    while (StackLen(s))
    {
        Pop(&s, &e);
        printf("%c", e);
    }
     
    getchar();
    getchar();
    getchar();
    return 0;
}