目录
骑马订式评价
算法思想
实现：
表达式评估
骑马订式
后缀表达式
括号法
后缀表达式的评价
算法思想
实现
骑马订式后缀式
算法思想
定义骑马订表达式评估算法思想个堆栈：
数据栈:s1、用于保存数字；
用于存储运算符的运算符栈:s2；
一个个地扫描字符元素，当遇到操作数时进入堆栈s1，
如果遇到运算符类型，则需要做出判断：
s2堆栈顶部元素运算符的优先级是否大于或等于当前运算符：
1 .成立：
在1.1中，s2堆栈顶部运算符的堆栈：假设堆栈是运算符a，此时，从s1开始堆栈两个数字b、c参加运算，将运算结果堆栈到s1；
1.2操作1.1个循环，直到堆顶元素不满足条件
1.3当前运算符的堆栈
2 .不成立：当前运算符进入堆栈
(直接进入s1，
遇到)，必须逐一取出这一对括号之间的运算符进行运算，使其与1.1的处理过程一致
3358 www.Sina.com/# include ' iostream ' # include ' stack ' # include ' cstring ' # include ' map ' usingnamespacestd； /**骑马订表达式求值*定义两个堆栈，在堆栈1中存储数值，在堆栈2中存储运算符，逐个扫描字符串str元素，遇到数字类型时堆栈stack1，遇到运算符类型时*堆栈2中的如果真的大于自己，则假设该运算符的堆栈是运算符a *，此时从堆栈1开始堆栈两个数字b、c以参与运算，并将运算结果堆栈到堆栈1中。 此时，此字符还无法进入堆栈。 如果堆栈顶的优先级仍然大于或等于自己，*则堆栈顶运算符检索运算，直到自己小于自己。 “”直接进入堆栈2，遇到“”() )、int y和char c )，然后提取括号之间的一个运算符。 int main () {堆叠int S1； //数字堆栈int S2； //符号堆栈//定义符号位优先级的映射int，int m； m[' ']=1； m['-']=1； m['*']=2； m['/']=2； m [ ' (' )=0； char bds[100]； cinbds； intlen=Strlen(BDS； int i=0；
while(i<len){ if(bds[i]>='0' && bds[i]<='9'){//数字 int num = 0; while (bds[i]>='0' && bds[i]<='9'){ num = num * 10 + bds[i] -'0'; i++; } s1.push(num); }else {//符号位 //处理符号位 if(bds[i]=='('){//符号位空，直接入栈,左括号，直接入栈 s2.push(bds[i]); }else if(bds[i]==')') {//右括号，符号位要一直出栈，直到,第一个(出现 while(s2.top()!='(') { int czs = s2.top();s2.pop(); int x = s1.top();s1.pop();//出两个操作数 int y = s1.top();s1.pop(); s1.push(cuclt(y,x,czs)); } s2.pop();//最后弹出左括号 }else{ while(s2.size()>0 && m[s2.top()] >= m[bds[i]]){//栈中的优先级大于当前符号 //出栈 int czs = s2.top();s2.pop(); int x = s1.top();s1.pop();//出两个操作数 int y = s1.top();s1.pop(); s1.push(cuclt(y,x,czs)); } s2.push(bds[i]); } i++; } } while (s2.size()){ //出栈 int czs = s2.top();s2.pop(); int x = s1.top();s1.pop();//出两个操作数 int y = s1.top();s1.pop(); s1.push(cuclt(y,x,czs)); } cout<<s1.top(); return 0;}int cuclt(int x,int y,char c){ int result = 0; if(c == '*'){ result = x*y; }else if(c == '/'){ result = x/y; }else if(c == '+'){ result = x+y; }else if(c == '-'){ result = x-y; } return result;}
表达式求值
表达式求值是程序设计语言编译中的一个最基本问题，也是信息学考察的一个基本知识点。
中缀表达式中缀表达式是一个通用的算术或逻辑公式表示方法。中缀表达式就是我们最常用的表达式形式，也是人最容易理解的表达式形式。
如： (a+b)*c-d 3*4+5/6
后缀表达式
后缀表达式右叫逆波兰式，是计算机比较容易处理的表达式形式
如：ab+c*d- 34*56/+
加括号法
有的时候我们需要快速将中缀表达式的形式转后缀表达式，例如初赛的选择题。我们可以采用加括号法：
1.根据运算符的优先级对中缀表达式加括号（有几个运算符就有几对括号）（原本有的括号不用加）
2.将运算符移到对应的括号后面
3.去掉所有括号，即为后缀表达式
以(a+b)*c-d为例：第一步先对运算符两边加括号：(((a+b)*c)-d)第二步针对每个括号，我们将运算符移动到括号后面：(((ab+)c*)d)-第三部去掉括号ab+c*d-
后缀表达式求值 算法思想
设置一个栈，开始时，栈为空，然后从左到右扫描后缀表达式，若遇操作数，则进栈；
若遇运算符，则从栈中退出两个元素，先退出的放到运算符的右边，后退出的 放到运算符左边，运算后的结果再进栈，直到后缀表达式扫描完毕。
此时，栈中仅有一个元素，即为运算的结果。
实现例如：
我们求3．5．2．-*7．+@的值
约定’@’为表达式的结束符号 ‘.’为操作数的结束符号。
核心代码如下：
stack<int> s; char c; int sum = 0; while(cin>>c && c!='@') {//扫描表达式字符串 if (c >= '0' && c <= '9') {//数字 sum = sum * 10 + c - '0'; } else if (c == '.') {//操作数结束，入栈 s.push(sum); sum = 0; } else {//操作符 int y = s.top(); s.pop(); int x = s.top(); s.pop(); s.push(cult(x, y, c)); } } cout<<s.top();
考虑下，如果首个操作数是负数，该怎么处理？
中缀表达式转后缀表达式 算法思想
中缀转后缀转换过程需要用到栈，具体过程如下：
从左到右扫描字符串
1）如果遇到操作数，我们就直接将其输出 。
2）如果遇到操作符，当栈为空直接进栈，不为空，判断栈顶元素操作符优先级是否比当前操作符小，小的话直接把当前操作符进栈，不小的话栈顶元素出栈输出，直到栈顶元素操作符优先级比当前操作符小
3）遇到左括号时我们也将其放入栈中。
4）如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号也要弹出
算法实现
#include "iostream"#include "queue"#include "map"#include "stack"#include "cstring"using namespace std;/** * 中缀表达式转后缀表达式 * @return */int main(){ char bds[1000]; map<char,int> yxj; queue<char> q; stack<char> s; yxj['*'] = 2; yxj['/'] = 2; yxj['+'] = 1; yxj['-'] = 1; cin>>bds; int len = strlen(bds); for (int i = 0; i <len ; ++i) { if(bds[i]>='0'&&bds[i]<='9'){//操作数直接进队列中 q.push(bds[i]); }else if(bds[i] == '(' || s.size() == 0){//左括号直接入栈 s.push(bds[i]); }else if(bds[i] == ')') {//右括号需要处理到上一个（位置 while(s.top()!='('){ q.push(s.top());s.pop(); } s.pop();//弹出左括号 }else{//操作符 while(s.size() && yxj[s.top()]>=yxj[bds[i]]){ q.push(s.top());s.pop(); } s.push(bds[i]); } } while (s.size()){//栈中可能还有操作符，需要输出 q.push(s.top());s.pop(); } while(q.size()){ cout<<q.front();q.pop(); } return 0;}
注意事项：
1）在此实现中，我们只是简单的把操作数放入了队列中，实际中可能是多位的操作数，输出方式可以能不同，需要具体情况具体对待
2）注意括号的处理