理论：
表达式的表示形式有中缀、前缀和后缀3中形式。中缀表达式按操作符的优先级进行计算（后面代码实现只包括+、-、*、\,小括号），即数学运算。后缀表达式中只有操作数和操作符。操作符在两个操作数之后。它的计算规则非常简单，严格按照从左到右的次序依次执行每一个操作。每遇到一个操作符，就将前面的两个数执行相应的操作。
由后缀表达式计算中缀表达式原理：计算机处理后缀表达式求值问题是比较方便的，即将遇到的操作数暂存于一个操作数栈中，凡是遇到操作数，便从栈中pop出两个操作数，并将结果存于操作数栈中，直到对后缀表达式中最后一个操作数处理完，最后压入栈中的数就是后最表达式的计算结果。
中缀表达式转换为等价的后缀表达式
中缀表达式不方便与计算机处理，通常要讲中缀表达式转换为一个与之等价的后缀表达式。等价是指两个表达式的计算顺序和计算结果完全相同。
中缀表达式：0.3/(5*2+1)#
的等价后缀表达式是：0.3 5 2 * 1 + /#
仔细观察这两个等价的表达式可知，操作数的出现次序是相同的，但运算符的出现次序是不同的。在后缀表达式中，运算符的出现次序是实际进行操作的次序；在中追表达式中，由于受到操作符的优先级和括号的影响，操作符出现次序与实际进行操作的次序很可能是不一样的。
算法描述：
将中缀表达式转换为等价的后缀表达式的过程要使用一个栈放“（”，具体可以按照下面的方式进行。
（1）从左到右一次扫描中缀表达式的每一个字符，如果是数字字符和圆点“.”则直接将它们写入后缀表达式中。
（2）如果遇到的是开括号“（”，则将它们压入一个操作符栈（不需要与栈顶操作符相比较），它表明一个新的计算层次的开始，在遇到和它匹配的闭括号“）”时，将栈中的元素弹出来并放入后缀表达式中，直到栈顶元素为“(”时，将栈顶元素“（”弹出（不需要加入后缀表达式），表明这一层括号内的操作处理完毕。
（3）如果遇到的是操作符，则将该操作符和操作符栈顶元素比较：
1、当所遇到的操作符的优先级小于或等于栈顶元素的优先级时，则取出栈顶元素放入后缀表式，
并弹出该栈顶元素，反复执行直到栈顶元素的优先级小于当前操作符的优先级；
2、当所遇到的操作符的优先级大于栈顶元素的优先级的时则将它压入栈中。
（4）重复上述步骤直到遇到中缀表达式的结束符标记“#”，弹出栈中的所有元素并放入后缀表达式中，转换结束。
C++ 代码描述算法：
(可以识别小数点，括号，实现加减乘除四则运算,可以处理任意长度的操作数，包括小数)
//MyStack.h
#include <iostream>
using namespace std;
template <class ElemType> class MyStack
{
public:
const static int MAXSIZE =100;
ElemType data[MAXSIZE];
int top;
public:
void init(); // 初始化栈
bool empty(); // 判断栈是否为空
ElemType gettop(); // 读取栈顶元素(不出栈)
void push(ElemType x); // 进栈
ElemType pop(); // 出栈
};
template<class T> void MyStack<T>::init()
{
this->top = 0;
}
template<class T> bool MyStack<T>::empty()
{
return this->top == 0? true : false;
}
template<class T> T MyStack<T>::gettop()
{
if(empty())
{
cout << "栈为空！\n";
exit(1);
}
return this->data[this->top-1];
}
template<class T> void MyStack<T>::push(T x)
{
if(this->top == MAXSIZE)
{
cout << "栈已满！\n";
exit(1);
}
this->data[this->top] =x;
this->top ++;
}
template<class T> T MyStack<T>::pop()
{
if(this->empty())
{
cout << "栈为空! \n";
exit(1);
}
T e =this->data[this->top-1];
this->top --;
return e;
}
// 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 "MyStack.h"
#include "PrefixToPostfix.h"
#include <iostream>
using namespace std;
void main()
{
MyStack<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");
}
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;
MyStack<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[])
{
MyStack<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();
}
运行结果：
转自:http://apps.hi.baidu.com/share/detail/21591676
完整代码见博文：http://blog.csdn.net/swkiller/article/details/6829386
分享到：
相关推荐
中缀表达式转换为后缀表达式，用堆栈实现！！！！！！！！
利用C语言实现中缀表达式转化为后缀表达式！！利用栈。
本程序是java堆栈的应用，实现中缀表达式转换成后缀表达式以及结果计算。
自定义栈，中缀表达式转换为后缀表达式并求值，三个抽象数据类型定义（1.class stack 2.class Middle_expressionToPost_expression 3.class Post_expression_value）
四川大学计算机学院-数据结构与算法分析高分实验报告-利用后缀表达式计算中缀表达式的值.rar 都是自己非常认真完成的，每一个要点都实现到位，还额外实现了创新内容。 最后得到的分数也很好
程序从标准输入上读入一行字符串，是一个合法的后缀表达式，数字和运算符之间由空格分隔。其中的数字可以是整数，也可以是带有小数部分的浮点数。 【输出形式】 向标准输出打印结果。 输出只有一行，是转换后的...
西南交通大学 报告仅供参考，请独立完成作业
中缀表达式转化为后缀表达式中缀表达式转化为后缀表达式
数据结构与算法分析高分实验报告-利用后缀表达式计算中缀表达式的值
这是一个基于栈实现的中缀表达式转换为后缀表达式的C++程序代码 支持+，-，*，/，%，（），代码仅供参考，有什么问题欢迎指出==
数据结构算法：中缀表达式转化为后缀表达式.doc 详细的论述和代码！
中缀表达式转换为后缀表达式，删除堆栈元素中缀表达式转换为后缀表达式，删除堆栈元素中缀表达式转换为后缀表达式，删除堆栈元素中缀表达式转换为后缀表达式，删除堆栈元素中缀表达式转换为后缀表达式，删除堆栈元素...
将中缀表达式，转换为后缀表达式和前缀表达式，再分别计算转换后的表达式值，比较两个计算结果，判断转换正确性和计算正确性。 ·编程 （1）读入中缀表达式，表达式的数据可以是实型、整型； （2）转换为后缀表达式...
用二叉树实现中缀表达式转换成后缀表达式，内含一个CPP文件的代码和一个截图，很不错的，是我自己写的。
编译系统对中缀表达式的处理方法是先把它转换为后后缀表达式.在后缀表达式中,运算符位于两个操作数的后面,并且没有括号,其运算符的次序就是其执行运算的次序。后缀表达式计算过程的规则非常简单：从左到右依次扫描，...
问题描述 中缀表达式就是我们通常所书写的数学表达式...要求：使用栈数据结构实现 ，输入的中缀表达式以＃号结束 输入 整数N。表示下面有N个中缀表达式 N个由单个字母和运算符构成的表达式 输出 N个后缀表达式。
栈的应用——表达式求解，内容主要有 中缀表达式转换成后缀表达式以及求解过程，需要可自行下载
本程序实现了输入任意一个中缀表达式，将其转换为后缀表达式的功能
用户输入中缀表达式，程序输出后缀表达式并输出计算结果
中缀表达式转化成后缀表达式并计算C++实现