0.引言

1.使用栈实现

#include <iostream>
#include <algorithm>
#include <fstream>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
using namespace std;#define  EmptyTOS -1
#define  MinStackSize  5#define ElementType double
/*************************栈的数组实现*********/
struct StackRecord;
typedef struct StackRecord  *Stack;struct StackRecord
{int Capacity;int TopOfStack;ElementType *Array;
};void MakeEmpty(Stack s)
{s->TopOfStack = EmptyTOS;
}void CreateStack(Stack *s,int MaxElements)
{Stack tmp;if (MaxElements < MinStackSize)cout << "Error! Stack is too small!" << endl;tmp = (Stack)malloc(sizeof(struct StackRecord));if (tmp == NULL)cout << "Error! out of space!" << endl;(tmp)->Array = (ElementType*)malloc(sizeof(ElementType)*MaxElements);if ((tmp)->Array == NULL)cout << "Error! out of space!" << endl;(tmp)->Capacity = MaxElements;MakeEmpty(tmp);*s = tmp;
}int IsEmpty(Stack s)
{return s->TopOfStack == EmptyTOS;
}void Push(ElementType x, Stack *s)
{(*s)->Array[++(*s)->TopOfStack] = x;//s->TopOfStack++;
}ElementType	 TopAndPop(Stack *s)
{if (!IsEmpty(*s))return (*s)->Array[(*s)->TopOfStack--];//先弹出再自减cout << "Error!Empty Stack!" << endl;return 0;
}/*************************后缀表达式*********/
const int MaxElement = 100;
bool IsNum(char *str)
{if ((*str >= '0' && *str <= '9') || *str == '.')return true;return false;
}double Char2Num(char *str)
{double n = 0.0;double tmp = 10.0;int flag = 0;assert(str);if(*str >= '0' && *str <= '9'){n = n * 10 + (*str - '0');str++;}else if (*str == '.'){str++;while (*str >= '0' && *str <= '9'){n = n + (*str - '0') / tmp;;tmp = tmp * 10;str++;}}return n;
}double Operation(char *src,Stack *stack)
{double tmp1 = 0.0, tmp2 = 0.0;tmp1 = TopAndPop(stack);tmp2 = TopAndPop(stack);switch (*src){case '+':return tmp1 + tmp2;case '-':return tmp1 - tmp2;case '*':return tmp1 * tmp2;case '/':return tmp1 / tmp2;default:break;}
}void PostFix(char *src,Stack *stack)
{double tmp0 = 0.0;while (*src != '\0'){if (IsNum(src)){tmp0 = Char2Num(src);Push(tmp0, stack);src++;}else{tmp0 = Operation(src, stack);Push(tmp0, stack);src++;}		}
}void PostFixTest()
{char Source1[] = "6523+8*+3+*";Stack stack;CreateStack(&stack, MaxElement);PostFix(Source1,&stack);cout << "result:" << endl;while (!IsEmpty(stack)){cout << TopAndPop(&stack) << " ";}cout << endl;
}int main(int argc, char **argv)
{//SymbolPairsTest();PostFixTest();system("pause");return 0;
}

只是实现了最简单的模式，对负数和小数还需更改。