程序代码：

编译原理上机实验—
中缀式构造后缀式
一．基础知识
中缀表达式到后缀表达式的转换
要把表达式从中缀表达式的形式转换成用后缀表示法表示的等价表达式，必须了解操作符的优先级和结合性。优先级或者说操作符的强度决定求值顺序；优先级高的操作符比优先级低的操作符先求值。如果所有操作符优先级一样，那么求值顺序就取决于它们的结合性。操作符的结合性定义了相同优先级操作符组合的顺序（从右至左或从左至右）。
转换过程包括用下面的算法读入中缀表达式的操作数、操作符和括号：
设立一个栈，存放运算符，首先栈为空，编译程序从左到右扫描中缀表达式，若遇到操作数，直接输出，并输出一个空格作为两个操作数的分隔符；若遇到运算符，则必须与栈顶比较，运算符级别比栈顶级别高则进栈，否则退出栈顶元素并输出，然后输出一个空格作分隔符；若遇到左括号，进栈；若遇到右括号，则一直退栈输出，直到退到左括号止。当栈变成空时，输出的结果即为后缀表达式。
二．基本要求
1．完成标准中缀算术表达式到后缀表达式的自动转换。
  2．中缀表达式由键盘输入，以回车键结束。
  3．输入的中缀表达式符合以下要求：

 （1）中缀表达式在逻辑上和结构上无错。

 （2）中缀表达式长度不确定但不超过128个。

 （3）中缀表达式仅出现在一行输入行中。

 （4）中缀表达式中只包含4种2目运算符：+，-，*，/   及两种优先级运算符“（”和“）”。

 （5）中缀表达式中的运算数由{a,b,…,z}中的单个字母或{0,1,…,8,9}中的单个数字。即一个运算数值包含一个字母或一位数字。

 （6）中缀表达式中不包含多余的空格。
  4．程序输出一行相应的后缀表达式。
二．源程序
/*设立一个栈，存放运算符，首先栈为空，编译程序从左到右扫描中缀表达式，
若遇到操作数，直接输出，并输出一个空格作为两个操作数的分隔符；
若遇到运算符，则必须与栈顶比较，运算符级别比栈顶级别高则进栈，否则退出栈顶元素并输出，然后输出一个空格作分隔符;
若遇到左括号，进栈；
若遇到右括号，则一直退栈输出，直到退到左括号止。当栈变成空时，输出的结果即为后缀表达式。*/
#include<iostream.h>
#include<stdio.h>
void main()
{
       char str[128];
       char stack[128];
       stack[0]=''1'';
       char *p;
       p=str;
       char *q;
       q=stack;
       cout<<"请输入待处理的中缀表达式!"<<endl;
       cout<<"输入的中缀表达式符合以下要求： "<<endl;
       cout<<"（1）中缀表达式在逻辑上和结构上无错。"<<endl;
       cout<<"（2）中缀表达式长度不确定但不超过128个。"<<endl;
       cout<<"（3）中缀表达式仅出现在一行输入行中。"<<endl;
       cout<<"（4）中缀表达式中只包含4种2目运算符：+，-，*，/及两种优先级运算符(和)。"<<endl;
       cout<<"（5）中缀表达式中的运算数由{a,b,…,z}{0,1,…,9}中的单个字母组成"<<endl;
       cout<<"（6）中缀表达式中不包含多余的空格。"<<endl;
       p=gets(str);//从键盘输入该表达式
       while(*p!=''\0'')
       {
              if((*p>=''a''&&*p<=''z'')||(*p>=''0''&&*p<=''9''))
              {
                     cout<<*p<<" ";
              }
              else
                     if(*p==''(''||*p=='')'')//左括号或者右括号
                     {
                            if(*p==''('')//左括号，进栈
                            {
                                   q++;
                                   *q=*p;
                            }
                            else//右括号，出栈到左括号
                            {
                                   while(*q!=''('')
                                   {
                                          cout<<*q<<" ";
                                          q--;
                                   }
                                          q--;
                            }

                     }
                     else
                     {
                            if(((*p==''*''||*p==''/'')&&(*q==''+''||*q==''-''))||*q==''1''||*q==''('')//优先级比栈顶高
                            {
                                   q++;
                                   *q=*p;
                            }
                            else
                            {
                                   cout<<*q<<" ";
                                   q--;
                                   p--;
                            }
                     }
              p++;
       }
       while(*q!=''1'')//栈中元素全部出栈
       {
              cout<<*q<<" ";
              q--;
       }
}


文章出处：飞诺网(www.):http://dev.

程序代码：

#include <iostream>
#include <cmath>
#include <ctype.h>
#include <stdlib.h>
using namespace std;
template <class T>
class Node
{
private:
    Node<T>* link;
public:
    T element;
    Node(T d=0,Node<T>* lk=0):element(d),link(lk)
    {}
     template<class Tpye> friend class Stack;
};
template <class T>
class Stack
{
private:
    Node<T>* top;
public:
    int size;
    Stack()
    {
        top=NULL;
        size=0;
    }
    ~Stack()
    {
        ClearStack();
        top=NULL;
    }
    bool IsEmpty() const
    {
        return size==0;
    }
    int Stacksize() const
    {
        return size;
    }
    bool Top(T& x) const
    {
        if(IsEmpty())
        {
            cout<<"Empty!!"<<endl;
            return false;
        }
        x=top->element;
        return true;
    }
    void Push(T x)
    {
        Node<T>* p;
        p=new Node<T>(x,top);
        top=p;
        size++;
    }
    T Pop()
    {
        if(size==0)
        {
            cout<<"没有元素为空！！"<<endl;
            exit(0);
        }
        Node<T> *p=top->link;
        T x=top->element;
        delete top;
        top=p;
        size--;
        return x;
    }
    void ClearStack()
    {
        Node<T> *p,*q;
        p=top;
        while(p!=NULL)
        {
            q=p;
            p=p->link;
            delete q;
        }
        size=0;
    }
};
int icp(char s)
{
    switch(s)
    {
    case '#': return 0;break;
    case '(': return 7;break;
    case '*' :case'/':return 4;break;
    case '+':case'-':return 2;break;
    case ')':return 1;break;
    case '^':return 6;break;
    default:
        cout<<"input error!"<<endl;break;
    }
}
int isp(char c)
{
    switch(c)
    {
    case '#': return 0;break;
    case '(': return 1;break;
    case '*' :case'/':return 5;break;
    case '+':case'-':return 3;break;
    case ')':return 7;break;
    case '^':return 4;break;
    default:
        cout<<"input error!"<<endl;break;
    }
}
double calculator()
{
    Stack<char> s1;
    Stack<double> s2;
    s1.Push('#');
    char ch;
    double x;
    cout<<"请输入中缀表达式，以符号#结束"<<"\n\n";
    while(cin>>ch)
    {

        if(isdigit(ch))
        {
            cin.putback(ch);
            cin>>x;
            s2.Push(x);
        }
        else
        {
            char z,w;
            for(int i=0;i<=s1.size+1;i++)
            {
                s1.Top(z);
                if(icp(ch)<isp(z))
                {
                    w=s1.Pop();
                    double x1,x2;
                    x2=s2.Pop();
                    x1=s2.Pop();
                    switch(w)
                    {
                    case '+': x1+=x2;break;
                    case '-': x1-=x2;break;
                    case '*': x1*=x2;break;
                    case '/': x1/=x2;break;
                    case '^': x1=pow(x1,x2);break;
                    }
                    s2.Push(x1);
                }
                else if(icp(ch)==isp(z))
                {
                    s1.Pop();break;
                }
                else
                {
                    s1.Push(ch);break;
                }
            }
            if(s1.size==0)
                break;
        }

    }
    double s;
    s2.Top(s);
    return s;
}
int main()
{
    double m;
    m=calculator();
    cout<<"计算结果为："<<"\n\n";
    cout.precision(10);
    cout<<m<<"\n\n";;
}