堆栈之表达式求值

对于整型表达式求值，如2+3*(45-1)-2使我们日常见到的中缀表达式，而对应的后缀表达式为 2 3 45 1 - * + 2 -，而后缀表达式处理计算相对来说比较简单，于是可以先将中缀表达式转化为后缀表达式，再计算后缀表达式，下面用堆栈来实现表达式求值。

第一步：中缀表达式转换为后缀表达式

一次从左向右扫描表达式，具体有以下6中情况：

1.遇到空格则认为是分隔符，直接跳过

2.若遇到数字则直接输出

3若遇到左括号则直接进栈

4若遇到右括号则不进栈，栈里运算符出栈并输出，当遇到左括号时停止出栈，此时左括号也出栈但不输出

5若遇到优先级比栈顶符号高的则直接进栈

6若遇到优先级比栈顶元素低或者相同的符号，则栈顶元素不断出栈，直到栈顶为空或者遇到比当前运算符号级别低的运算符停止出栈，再将此运算符进栈

第二步：处理后缀表达式,从左向右扫描

1.遇到云算数则直接进栈

2遇到运算符，则将堆栈中抛出两个数字做运算，再将运算结果进栈

3最终栈中留下的一个数字就是计算的结果，将其直接出栈

//表达式求值
#include<iostream>
#include<stack>
#include<string>
#include<cmath>
using namespace std;
int Rank(char ch);
string Transform(string s); //将中缀表达式转变为后缀表达式
int Caculate(string s); //计算后缀表达式
int main(){
string s1, s2;
getline(cin,s1);
s2 = Transform(s1);
int result = Caculate(s2);
cout << result << endl;
return 0;
}
int Rank(char ch){
if (ch == ‘+‘ || ch == ‘-‘)
return 1;
if (ch == ‘*‘ || ch == ‘/‘)
return 2;
if (ch == ‘(‘) //有必要为啦不至于没有遇到‘)‘就导致‘(‘输出
return 0;
}
string Transform(string s){
int i, m;
char ch[100];
stack<char> C;
m = 0;
for (i = 0; i < s.size(); i++){
if (s[i]== ‘ ‘)
continue;
if (s[i] < ‘0‘ + 10 && s[i] >= ‘0‘){ //如果是数字直接输出
while (s[i] < ‘0‘ + 10 && s[i] >= ‘0‘){
ch[m] = s[i];
i++;
m++;
}
ch[m] = ‘ ‘;
m++;
i--; //为了保持i一致
}
else{ //否则就是运算符啦
if (C.empty()) //如果为空,直接进栈
C.push(s[i]);
else if (s[i] == ‘)‘){ //当扫描到‘)‘的时候
while (C.top() != ‘(‘){ //直到遇到‘(‘结束
ch[m] = C.top();
m++;
C.pop(); //出栈
}
C.pop(); //‘(‘也出栈，但是不输出
}
else if (s[i] == ‘(‘){
C.push(s[i]); //左括号直接压入栈中
}
else if (Rank(s[i]) > Rank(C.top())) //若扫描到的比栈顶优先级高则进栈
C.push(s[i]);
else{ //否则就要出栈
while (!C.empty()&&Rank(s[i]) <= Rank(C.top())){//不可以改成Rank(s[i]) <=Rank(C.top())&&!C.empty()，否则可能倒置指针越界
ch[m] = C.top();
m++;
C.pop(); //出栈
}
C.push(s[i]); //当遇到比s[i]优先级高的时候将s1压入栈中
}
}
}
while (!C.empty()){ //如果堆栈里面还有元素，则全部输出
ch[m] = C.top();
m++;
C.pop();
}
string s1(ch, 0, m);
return s1;
}
int Number(string&s, int&i){ //将字符转变为数字
int j, m,q=0;
int a[10] = { 0 };
m = 0; //m记录数字长度
for (j = i; s[j] >= ‘0‘&&s[j] < ‘0‘ + 10;j++){
a[m] = s[j] - ‘0‘;
m++;
}
i = j - 1; //i还原一位
for (j = 0; j < m; j++)
q += a[j] * pow(10, m - j - 1);
return q;
}
int Caculate(string s){
int i, k,a,b;
stack<int>v;
for (i = 0; i < s.size(); i++){ //扫描后缀表达式s
if (s[i] == ‘ ‘)
continue;
else if (s[i] < ‘0‘ + 10 && s[i] >= ‘0‘)//如果遇到数字,直接进栈
v.push(Number(s, i));
else{
a = v.top(), v.pop();
b = v.top(), v.pop(); //a,b出栈做相应运算
switch (s[i]){
case ‘+‘:v.push(a + b); break;
case ‘-‘:v.push(b - a); break;
case ‘*‘:v.push(a*b); break;
case ‘/‘:v.push(b / a); break;
}
}
}
return v.top();
}

堆栈之表达式求值

原文：http://www.cnblogs.com/td15980891505/p/4853605.html