目录

中缀表达式求值

算法思想

实现：

表达式求值

中缀表达式

后缀表达式

加括号法

后缀表达式求值

算法思想

实现

        中缀表达式转后缀表达式

算法思想

中缀表达式求值

算法思想

定义两个栈：

数据栈：s1，用以存储数字；

运算符栈：s2，用以存储运算符；

将字符元素一个个扫描，遇到操作数则进栈s1，

遇到运算符型，需要判断：
s2栈顶元素运算符优先级是否比当前运算符大或等于：
1. 成立：
    1.1 那么s2栈顶运算符出栈：假设出栈是运算符a，那么此时从s1中出栈两个数字b、c参与运算，把运算结果进栈s1；
    1.2 循环1.1操作，直到栈顶元素不满足条件
    1.3 当前运算符入栈
2. 不成立：当前运算符入栈

遇到(直接进s1，
遇到)则就要把这一对括号之间运算符都一个个拿出来运算,与1.1处理过程一致

实现：

#include "iostream"
#include "stack"
#include "cstring"
#include "map"
using namespace std;/*** 中缀表达式求值* 定义两个栈，stack1存储数字，stack2存储运算符，将字符串str元素一个个扫描，遇到数字型则进栈stack1，遇到运算符型，* 则要看看栈stack2栈顶元素运算符优先级是否比自己大或等于，如果真比自己大，那么那个运算符出栈，假设出栈是运算符a，* 那么此时从stack1中出栈两个数字b、c参与运算，把运算结果进栈stack1，此时此字符还不能进栈，如果栈顶优先级还比自己大或等于，* 那么那个栈顶运算符还要拿出来运算，直到有小于自己的自己才进栈；遇到‘（’直接进stack2，遇到’）’，则就要把这一对括号之间运算符都一个个拿出来运算* @return*/int cuclt(int x,int y,char c);int main(){stack<int> s1;//数字栈stack<int> s2;//符号栈//定义符号位的优先级map<int,int> m;m['+'] = 1;m['-'] = 1;m['*'] = 2;m['/'] = 2;m['('] = 0;char bds[100];cin>>bds;int len = 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）注意括号的处理