中缀表达式：a+b*c+(d*c+f)*g
相应的后缀表达式：abc*+de*f+g*+
转化思想：
1. 输出 a b 栈 + (栈空,+入栈)
2.输出 abc 栈 +* （*的优先级比+高，*入栈）
3.输出 abc*+ 栈 + （+的优先级低于栈顶的*，*出栈，+的优先级不高于栈顶的+，栈顶+出栈，+入栈）
4.输出abc*+d 栈+（ （'('具有最高优先级，因此入栈）
5.输出abc*+de 栈+（* （由于除非正在处理闭括号，否则开括号不会从栈中弹出）
6.输出abc*+de*f 栈+（+ （+的优先级低于栈顶的*，*出栈，+入栈）
7.输出abc*+de*f+ 栈+ （读入‘）’，弹出栈元素直到‘（’）
8.输出abc*+de*f+g 栈+*
9.输出abc*+de*f+g*+ 栈 （由于输入为空，栈中元素全部弹出）
后缀表达式的计算，例子6 5 2 3 + 8 * + 3 + *
栈的变化如下：
6 5 2 3
6 5 5 （5=2+3）
6 5 5 8
6 5 40 （40=5*8）
6 45 （45=40+5）
6 45 3
6 48 （48=45+3）
288 （288=6*48）
#include <iostream>
#include<stack>
#include<string>
#include<vector>
#include<cstdlib>
using namespace std;
//判断运算符的优先级
int pro ( char c )
{
int p = 0;
switch ( c )
{
case '+':
case '-':
p = 1;
break;
case'*':
case'/':
p = 2;
break;
case'(':
case')':
p = 0;
break;
}
return p;
}
//运算符号入栈\出栈
void enterstack ( stack<char> & cs , char c, vector<string> & s1 )
{
char p;
string s;
if ( cs.empty() || c == '(' )
cs.push ( c );
else if ( c == ')' )
{
while ( cs.top() != '(' )
{
s = cs.top();
s1.push_back ( s );
cs.pop();
}
cs.pop();
}
else if ( c == '=' )
{
while ( !cs.empty() )
{
s = cs.top();
s1.push_back ( s );
cs.pop();
}
}
else
{
p = cs.top();
if ( pro ( c ) > pro ( p ) )
cs.push ( c );
else
{
s = p; //char转化为string
s1.push_back ( s );
cs.pop();
enterstack ( cs, c, s1 );
}
}
}
//中缀表达式转化成后缀表达式
void pretosuf ( string &s, vector<string> & s1 )
{
stack<char> cs;//栈，运算符号
string str; //将char转化成string
for ( int i = 0, j = 0; i < s.size(); i++ )
{
int flag = 0;
while ( s[i] <= '9' && s[i] >= '0' || s[i] == '.' )
{
str = s[i];
if ( flag == 0 )
{
s1.push_back ( str );
j = s1.size();
flag = 1;
}
else
{
s1[j - 1] += s[i];
}
i++;
}
enterstack ( cs, s[i], s1 ); //运算符号输出 or 入栈
str = s[i];
if ( s[i] == '=' )
{
s1.push_back ( str );
break;
}
}
}
//计算后缀表达式结果
double calculator ( vector<string> &s )
{
stack<double> data;
double d, a, b;
for ( int i = 0; s[i] != "="; i++ )
{
if ( s[i] == "+" )
{
a = data.top();
data.pop();
b = data.top();
data.pop();
data.push ( a + b );
}
else if ( s[i] == "-" )
{
a = data.top();
data.pop();
b = data.top();
data.pop();
data.push ( b - a );
}
else if ( s[i] == "*" )
{
a = data.top();
data.pop();
b = data.top();
data.pop();
data.push ( a * b );
}
else if ( s[i] == "/" )
{
a = data.top();
data.pop();
b = data.top();
data.pop();
data.push ( b / a );
}
else
{
d = atof ( s[i].c_str() );
data.push ( d );
}
}
return data.top();
}
int main()
{
vector<string> str;
string s;
double sum;
getline ( cin, s );
pretosuf ( s, str );//中缀表达式转化为后缀表达式
sum = calculator ( str );//计算后缀表达式
cout << sum << endl;
return 0;
}
运行结果
