数学表达式转换成后缀式(逆波兰式),对后缀式进行计算,

Question

编写程序实现将输入的数学表达式转换成后缀式(逆波兰式),并对后缀式进行计算,输出得到的值。
测试数据 ：
输入 3*(7-5)+(4+8)/3#
输出
后缀式：3$7$5$-*4$8$+3$/+#
结果：-2

实验目的 实验思路
对实验的分析 讨论及实验总结
不要你写程序
就简单的说下实验目的 实验思路
对实验的分析 讨论 及实验总结就行

Answer 1

中缀表达式如1*2+(2-1), 其运算符一般出现在操作数之间, 因此称为中缀表达式,也就是大家编程中写的表达式。编译系统不考虑表达式的优先级别, 只是对表达式从左到右进行扫描, 当遇到运算符时, 就把其前面的两个操作数取出, 进行操作。为达到上述目的, 就要将中缀表达式进行改写,变为后缀表达式 如上面的表达式

1*2+(2-1), 就变为12*21-+;

后缀表达式中不含有括号, 且后缀表达式的操作数和中缀表达式的操作数排列次序完全相同, 只是运算符的次序发生了改变。我们实现的时候，只需要用一个特定工作方式的数据结构（栈），就可以实现。

其中stack op;用来存放运算符栈。数组ans用来存放后缀表达式。

算法思想：

从左到右扫描中缀表达式，是操作数就放进数组ans的末尾。

如果是运算符的话，分为下面3种情况：

1）如果是‘（’直接压入op栈。

2）如果是‘）’，依次从op栈弹出运算符加到数组ans的末尾，知道遇到'（'；

3) 如果是非括号，比较扫描到的运算符，和op栈顶的运算符。如果扫描到的运算符优先级高于栈顶运算符

则，把运算符压入栈。否则的话，就依次把栈中运算符弹出加到数组ans的末尾，直到遇到优先级低于扫描

到的运算符，并且把扫描到的运算符压入栈中。

就这样依次扫描，知道结束为止。

如果扫描结束，栈中还有元素，则依次弹出加到数组ans的末尾，就得到了后缀表达式。

我空间里面有详细介绍，中缀转换后缀的代码和问题描述，主要是理解算法的思想，和数据结构，这样才算掌握了。
http://hi.baidu.com/huifeng00/blog/item/70cb280dabd9d4216059f3d1.html

Answer 2

逆波兰式也叫后缀表达式(将运算符写在操作数之后)
如：我们平时写a+b，这是中缀表达式，写成后缀表达式就是：ab+
(a+b)*c-(a+b)/e的后缀表达式为：
(a+b)*c-(a+b)/e
→((a+b)*c)((a+b)/e)-
→((a+b)c*)((a+b)e/)-
→(ab+c*)(ab+e/)-
→ab+c*ab+e/-

试验目的
对于实现逆波兰式算法，难度并不大，但为什么要将看似简单的中序表达式转换为复杂的逆波兰式？原因就在于这个简单是相对人类的思维结构来说的，对计算机而言中序表达式是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。通过试验掌握栈的数据结构在计算机中应用。

试验思路
将一个普通的中序表达式转换为逆波兰表达式的一般算法是：
1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。
(2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。
(3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。
(4)如果不是数字，该字符则是运算符，此时需比较优先关系。
做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将栈顶的运算符从栈中弹出，直到栈顶运算符的优先级低于当前运算符，将该字符入栈。
(5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。

下面以(a+b)*c为例子进行说明：
(a+b)*c的逆波兰式为ab+c*，假设计算机把ab+c*按从左到右的顺序压入栈中，并且按照遇到运算符就把栈顶两个元素出栈，执行运算，得到的结果再入栈的原则来进行处理，那么ab+c*的执行结果如下：
1）a入栈（0位置）
2）b入栈（1位置）
3）遇到运算符“+”，将a和b出栈，执行a+b的操作，得到结果d=a+b，再将d入栈（0位置）
4）c入栈（1位置）
5）遇到运算符“*”，将d和c出栈，执行d*c的操作，得到结果e，再将e入栈（0位置）
经过以上运算，计算机就可以得到(a+b)*c的运算结果e了。

试验分析
逆波兰式除了可以实现上述类型的运算，它还可以派生出许多新的算法，数据结构，这就需要灵活运用了。逆波兰式只是一种序列体现形式。

Answer 3

1 读入运算对象，直接输出

2 ( 运算符进栈

3 ) 运算符，栈内的最上一个( 以上的运算符退栈，(也退栈
4 读入运算符，进入运算栈
4.1 后进栈的运算符 > 先进栈的运算符，运算符进栈 (优先级比较)
4.2 后进栈的运算符 <= 先进栈的运算符，将栈内的运算符退栈输出，再进栈
5 # 结束符

这里关键是运算符的优先级，运算符比较少比较简单，否则确定相互的优先级可能会麻烦点。'('是个特殊的符号，一直留在栈中直至‘)’出现，它不受优先级进出栈的影响。代码如下：

#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;

int getPriority(char Op);

int main()
{
int n = 0;
char op = 0;
string expr;
stack<char> operators;
cin >> n;
getline(cin,expr);
while(n > 0)
{
getline(cin,expr);
expr.push_back(')');

operators.push('(');
for (int i = 0; i < expr.size(); ++i)
{
// if is operands
if ((expr[i] >= 'a')&&
(expr[i] <= 'z'))
{
cout << expr[i];
continue;
};
// if is ')'
if (expr[i] == ')')
{
while(operators.top() != '(')
{
cout << operators.top();
operators.pop();
};
operators.pop();
continue;
};
// if nomarl operators
if ((getPriority(expr[i]) <= getPriority(operators.top())) &&
(expr[i] != '('))
{
cout << operators.top();
operators.pop();
}
operators.push(expr[i]);
};
--n;
cout << endl;
};
return 0;
};

int getPriority(char op)
{
switch(op)
{
case '(':
return 0;
break;
case '+':
return 1;
break;
case '-':
return 2;
break;
case '*':
return 3;
break;
case '/':
return 4;
break;
case '^':
return 5;
break;
default:
return 5;
break;
};
};

参考资料：http://archerzz.spaces.live.com/blog/cns!619C7A4B0A10FE1F!126.entry

Answer 4

一、问题的描述以及设计思路
1、问题的描述
表达式计算是掌握程序设计语言的重要部分之一，也是堆栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。为增加系统设计的可扩展性，对本设计系统增加乘方（^）运算，以及增加对小数的支持能力。系统测试采用题目要求的数据，同时测试系统对乘方以及对小数的支持，自己增加测试数据。以达到系统设计的正确性。同时为提高自己编写实际应用程序的能力，为以后的学习以及就业作好准备，在程序的编写中尽量与专业的编程规范靠拢，本系统代码的书写采用结构化的编程方式，力求设计代码以及注释等规范，符合要求，同时提高自己的编程能力。
2、设计思路
系统设计题目的要求是使用堆栈，完成算术表达式的由中缀表达式转换成后缀表达式，为以后的表达式求值做准备。实验中最重要的部分我认为应当是表达式的转换过程，通过运算符优先级别的比较完成后缀表达式的转换。运算符的优先级的比较通过特定的表格形式形成直观的概念，增加对乘方的支持，在实际设计过程中体现的是优先级比较函数。由于本系统中增加了对小数部分的支持，不仅仅局限于一位整数部分。因此对小数部分的转换也是本系统设计的一个难点。设计思路的详细表达为以下内容：
a) 、定义一个字符型数组，要求数组足够大，能够完全存放下输入的表达式。
b) 、定义一个运算符优先级比较的函数，并且完成函数的设计。
c) 、依次扫描输入的字符序列，当扫描到的是数字时，放入已事先定义好的字符型的队列中。
d) 、将字符型队列的元素值转化成双精度型数据并且存放在另外一个堆栈中。
e) 、当扫描到的是运算符时，进行运算，取堆栈中的两个double型数据作为运算数。将运算结果压栈，作为以后运算的操作数。
f) 当字符序列扫描完成以后，堆栈中存放的就是最后的运算结果，将运算结果进行输出，即得到最终结果。

二、设计的详细过程
。。。。
代码略
。。。

三、结论及体会
1、实验结论
a)、实验完成了题目的要求，并且根据实际情况增加了对小数的支持。而输入的数字的个数也不限制于一位，扩展到多位，具体位数由双精度数的限制决定。
b)、编写代码基本上能够满足编程规范的要求，代码的变量命名，以及注释的书写，基本能按照要求进行。
b)、将数据结构中的队列和堆栈的知识复习到，并且学会创新，在代码的编写中，学习了编程规范，学习了结构化编程。

2、实验体会
a)、通过本设计实验将数据结构中的堆栈和队列的知识复习到，并且能够自己设计一些东西，学会了在设计实验过程时的基本步骤。基本上能够有条理的解决这些问题。
b)、在试验中遇到了很多的问题，都是以前没有发现的，这些问题设计的方面很多，有以前的C++基础的，也有最近学习的数据结构的知识。通过实验的设计，让我发现了自己的不足。自己在学习知识上面的漏洞。希望通过弥补这些发现的漏洞，提高自己的专业知识水平。
c)、设计过程中的解决问题的方法，让我明白了如何学习会更有效。如何学习才不会耽误太多的时间。也学会了解决问题的一般方法：向老师、同学请教，借助网络等等。
d)、实验过程中也走了很多的弯路，由于在开始设计的时候思路不时很清晰，对于一些问题不能很好的提出解决问题的方法，在设计过程中，代码总是重复的修改，并且由于不能再以各高度上给自己编写的代码进行一个评价，在很多问题上，代码并不时最优的。相信在以后的学习中，随着知识的增多，问题会逐渐得到解决。

Answer 5

栈的运用