//expseqstack.h

//10只是示例性的数据，可以根据实际问题具体定义

const int StackSize=10;  typedef struct{	char op;	int inputprecedence;	int stackprecedence;}DataType1;template <class T>       //定义模板类SeqStackclass SeqStack{public:    SeqStack();            //构造函数，栈的初始化	~SeqStack();            //析构函数	void init();    void Push(T x);          //将元素x入栈    T Pop();                //将栈顶元素弹出    T GetTop();	         //取栈顶元素（并不删除）	bool Empty();           //判断栈是否为空public:    T data[StackSize];      //存放栈元素的数组    int top;                //栈顶指针，指示栈顶元素在数组中的下标};/* * 前置条件：栈不存在 * 输    入：无 * 功    能：栈的初始化 * 输    出：无 * 后置条件：构造一个空栈 */template <class T>SeqStack<T>::SeqStack(){	top=-1;}/* * 前置条件：栈已存在 * 输    入：无 * 功    能：销毁栈 * 输    出：无 * 后置条件：释放栈所占用的存储空间 */template <class T>SeqStack<T>::~SeqStack(){} template <class T>void SeqStack<T>::init(){	top=0;} /* * 前置条件：栈已存在 * 输    入：元素值x * 功    能：在栈顶插入一个元素x * 输    出：如果插入不成功，抛出异常 * 后置条件：如果插入成功，栈顶增加了一个元素 */template <class T> void SeqStack<T>::Push(T x){    if (top== StackSize-1) throw "上溢";    top++;    data[top]=x;}/* * 前置条件：栈已存在 * 输    入：无 * 功    能：删除栈顶元素 * 输    出：如果删除成功，返回被删元素值，否则，抛出异常 * 后置条件：如果删除成功，栈顶减少了一个元素 */     template <class T>T SeqStack<T>::Pop(){     T x;    if (top==-1) throw "下溢";    x=data[top--];    return x;}/* * 前置条件：栈已存在 * 输    入：无 * 功    能：读取当前的栈顶元素 * 输    出：若栈不空，返回当前的栈顶元素值 * 后置条件：栈不变 */template <class T> T SeqStack<T>::GetTop(){	if (top!=-1)      return data[top];}/* * 前置条件：栈已存在 * 输    入：无 * 功    能：判断栈是否为空 * 输    出：如果栈为空，返回1，否则，返回0 * 后置条件：栈不变 */template <class T> bool SeqStack<T>::Empty(){	if(top==-1) return 1;	else return 0;} 

//main.cpp#include"expseqstack.h"#include<iostream>#include<string>using namespace std;//检查符号之间的优先级，1表示>,0表示=，-1表示<，c1栈内的运算，c2栈外的运算  int check(char c1, char c2)  {      int a1, a2;      if (c1 == ‘+‘ || c1 == ‘-‘)          a1 = 3;      if (c1 == ‘*‘ || c1 == ‘/‘)          a1 = 5;      if (c1 == ‘(‘)          a1 = 1;      if (c1 == ‘)‘)          a1 = 7;      if (c1 == ‘#‘)          a1 = 0;        if (c2 == ‘+‘ || c2 == ‘-‘)          a2 = 2;      if (c2 == ‘*‘ || c2 == ‘/‘)          a2 = 4;      if (c2 == ‘(‘)          a2 = 6;      if (c2 == ‘)‘)         a2 = 1;      if (c2 == ‘#‘)          a2 = 0;        if (a1 > a2)          return 1;      if (a1 == a2)          return 0;      if (a1 < a2)          return -1;  }    //符号运算函数  double sum(char c, double d1, double d2)  {      switch (c)      {      case ‘+‘:          return d1 + d2;          break;      case ‘-‘:          return d1 - d2;          break;      case ‘*‘:          return d1 * d2;          break;      case ‘/‘:          return d1 / d2;         break;      default:          break;      }  }    int main()  {     char *op = "+-*/()#";      string str;      cout<<"请输入表达式："<<endl;	cin>>str;  	   //给表达式字符串str添加‘#’结束标志符      str.append(1, ‘#‘);      SeqStack<char> OPTR;//运算符栈     SeqStack<double> OPND;//操作数栈      int a = -1;      //先将‘#‘入栈     OPTR.Push(‘#‘);      while (true)     {          int b = a + 1;          a = str.find_first_of(op, a + 1);          if (a == string::npos)             break;          if (a != b)         {              string ss(str, b, a - b);              double d = atof(ss.c_str());              //数据先入栈              OPND.Push(d);          }          //运算符优先级比较          char val;          val=OPTR.GetTop();          int che = check(val, str[a]);            if (-1 == che)//栈外优先级大直接入栈            {                OPTR.Push(str[a]);            }            if (0 == che)//栈内外优先级相等则出栈            {                OPTR.Pop();            }            if (1 == che)//栈内优先级大，出栈进行运算            {                char val;  double d1;    double d2;                val=OPTR.GetTop();                              d1=OPND.GetTop();                d1=OPND.Pop();                            d2=OPND.GetTop();                d2=OPND.Pop();                d1 = sum(val, d2, d1);                //运算结果入栈                OPND.Push(d1);                OPTR.Pop();                a--;            }      }      double s;      s=OPND.GetTop();      cout <<s<<endl;      return 0;  }  

//头文件 PrefixToPostfix.h#include <vector>  using namespace std;  bool isoperator(char op);                         // 判断是否为运算符  int priority(char op);                            // 求运算符优先级  void postfix(char pre[] , char post[],int &n);    // 把中缀表达式转换为后缀表达式  double read_number(char str[],int *i);            // 将数字字符串转变成相应的数字  double postfix_value(char post[]);                // 由后缀表达式字符串计算相应的中值表达式的值   

//PrefixToPostfix.cpp#include "PrefixToPostfix.h"  #include"expseqstack.h"#include <iostream>  using namespace std;  bool isoperator(char op)  {     switch(op)      {      case ‘+‘:      case ‘-‘:      case ‘*‘:      case ‘/‘:          return 1;      default :           return 0;     }  }    int priority(char op)  {     switch(op)      {      case ‘#‘:          return -1;      case ‘(‘:          return 0;      case ‘+‘:      case ‘-‘:          return 1;      case ‘*‘:      case ‘/‘:          return 2;      default :         return -1;      }  } //   把中缀表达式转换为后缀表达式，返回后缀表达式的长度（包括空格）  void postfix(char pre[] ,char post[],int &n)  {      int i = 0 ,j=0;      SeqStack<char> stack;      stack.init();       // 初始化存储操作符的栈        stack.Push(‘#‘);    // 首先把结束标志‘#’放入栈底        while(pre[i]!=‘#‘)      {          if((pre[i]>=‘0‘ && pre[i] <=‘9‘)||pre[i] ==‘.‘) // 遇到数字和小数点直接写入后缀表达式          {              post[j++] = pre[i];              n++;          }          else if (pre[i]==‘(‘)   // 遇到“（”不用比较直接入栈              stack.Push(pre[i]);          else if(pre[i] ==‘)‘)  // 遇到右括号将其对应左括号后的操作符（操作符栈中的）全部写入后缀表达式          {              while(stack.GetTop()!=‘(‘)             {                 post[j++] = stack.Pop();                 n++;              }             stack.Pop(); // 将“（”出栈，后缀表达式中不含小括号          }         else if (isoperator(pre[i]))          {              post[j++] = ‘ ‘; // 用空格分开操作数(             n++;              while(priority(pre[i]) <= priority(stack.GetTop()))               {                  // 当前的操作符小于等于栈顶操作符的优先级时，将栈顶操作符写入到后缀表达式，重复此过程                  post[j++] = stack.Pop();                 n++;              }                stack.Push(pre[i]); // 当前操作符优先级大于栈顶操作符的优先级，将该操作符入栈          }           i++;      }      while(stack.top) // 将所有的操作符加入后缀表达式      {         post[j++] = stack.Pop();         n++;     }  }    double read_number(char str[],int *i)  {     double x=0.0;      int k = 0;     while(str[*i] >=‘0‘ && str[*i]<=‘9‘)  // 处理整数部分      {          x = x*10+(str[*i]-‘0‘);          (*i)++;      }        if(str[*i]==‘.‘) // 处理小数部分     {          (*i)++;         while(str[*i] >= ‘0‘&&str[*i] <=‘9‘)          {           x = x * 10 + (str[*i]-‘0‘);             (*i)++;              k++;          }      }      while(k!=0)      {          x /= 10.0;          k--;     }       return x;  }   double postfix_value(char post[])  {      SeqStack<double> stack;    // 操作数栈      stack.init();        int i=0 ;     double x1,x2;       while(post[i] !=‘#‘)      {         if(post[i] >=‘0‘ && post[i] <=‘9‘)             stack.Push(read_number(post,&i));          else if(post[i] == ‘ ‘)              i++;          else if (post[i] ==‘+‘)          {              x2 = stack.Pop();              x1 = stack.Pop();              stack.Push(x1+x2);              i++;          }          else if (post[i] ==‘-‘)          {              x2 = stack.Pop();              x1 = stack.Pop();              stack.Push(x1-x2);              i++;          }          else if (post[i] ==‘*‘)          {              x2 = stack.Pop();            x1 = stack.Pop();              stack.Push(x1*x2);             i++;          }          else if (post[i] ==‘/‘)          {              x2 = stack.Pop();             x1 = stack.Pop();              stack.Push(x1/x2);              i++;          }      }      return stack.GetTop();  }  

//main.cpp#include "PrefixToPostfix.h"  #include"expseqstack.h"#include <iostream>  using namespace std;  void main()  {      SeqStack<int> stack ;     stack.init();       //char pre[] ="22/(5*2+1)#";      char exp[100];      cout << "输入表达式(中缀，以#结束)：";      cin >> exp;       char post[100] ;      //cout <<"中缀表达式为："<< pre << endl;        int n =0;           // 返回后缀表达式的长度     postfix(exp,post,n);      cout <<"后缀表达式为：";     for( int i =0 ;i < n ;i++)         cout << post[i] ;        cout << "\n由后缀表达式计算出的数值结果:  ";     cout << postfix_value(post) << endl;       system("pause");  }