中缀表达式变成后缀表达式并求值 - 数据结构与算法

热情依然

等　级：版主
威　望：22
帖　子：715
专家分：0
注　册：2005-4-5

楼主

问题点数：0 回复次数：35

中缀表达式变成后缀表达式并求值

//以下程序更新了以前的程序，添加了后缀表达式运算的过程。

#include <iostream>
#include <string>
#include <stack>
#include <vector>

namespace{

class Expression
{
public:
Expression();
static void Remove_space(std::string &Translated);
static int Compare(char op);
static void RPN(std::string expression);
static int Clculate();
static void Display(const std::vector<int> &opnd, const std::string &soper);

static std::vector<std::string> sResult;
static std::stack<int> snum;
};
std::vector<std::string> Expression::sResult;
std::stack<int> Expression::snum;

Expression::Expression()
{
sResult.reserve(100);
}

void Expression::Remove_space(std::string &Translate)
{
std::string::size_type position_start = 0;
std::string::size_type position_end = 0;

std::string Result;
Result.reserve(100);
while( (position_end = Translate.find_first_of(' ',position_start)) != std::string::npos)
{
std::string temp = Translate.substr(position_start,position_end - position_start);
Result += temp;
position_start = ++position_end;
}
Result += Translate.substr(position_start,position_end - position_start);
Translate = Result;
}

int Expression::Compare(char op)
{
int Level = 0;
switch(op)
{
case '+':case '-':
Level = 1;
break;
case '*':case '/':
Level = 2;
break;
default:
break;
}
return Level;
}

void Expression::RPN(std::string expression)
{
std::string::size_type nCount = expression.length();
std::string::size_type index = 0;
std::stack<char> stmp;
bool flag = false;

stmp.push('@');
while( index < nCount)
{
if( expression[index] == '(')
{
stmp.push('(');
index++;
}
else if( expression[index] == ')')
{
while( stmp.top() != '(')
{
sResult.push_back( std::string(1, stmp.top()) );
stmp.pop();
}
stmp.pop();
index++;
}
else if( expression[index] == '+' || expression[index] == '-' ||
expression[index] == '*' || expression[index] == '/' )
{
if( expression[index] == '-' || expression[index] == '+' )
{
if(index == 0)//如果第一个数字是负数
{
index ++;
flag = true;
}
else if( expression[index-1] == '(' )//如果括号里第一个数是负数
{
index++;
flag = true;
}
else
{
while( Compare( expression[index] ) <= Compare( stmp.top() ))
{
sResult.push_back( std::string(1, stmp.top()) );
stmp.pop();
}

stmp.push( expression[index] );
index++;
}

}
else
{
while( Compare( expression[index] ) <= Compare( stmp.top() ))
{
sResult.push_back( std::string(1, stmp.top()) );
stmp.pop();
}
stmp.push( expression[index] );
index++;
}
}
else
{
std::string temp;
if(flag == true)
{
temp += expression[index - 1];
flag = false;
}
while( expression[index] >= '0' && expression[index] <= '9')
{
temp += expression[index];
index ++;
}
sResult.push_back( temp );
}
}//while

while(stmp.top() != '@')
{
if(stmp.top() == '(')
{
std::cout << "Error in expression" << std::endl;
exit(-1);
}
sResult.push_back( std::string(1, stmp.top()) );
stmp.pop();
}

}//RPN

int Expression::Clculate()
{
std::vector<int> opnd;

size_t index = 0;

int num1 = 0, num2 = 0;

std::cout<< "OPND栈" << "\t\t" <<"OPTR栈" << "\t\t" <<"输入字符"<<"\t"<<"主要操作"<<std::endl;

for(index = 0; index < sResult.size(); ++index)
{
std::string oper = sResult[index];
if( (oper.size()>1) && (oper[0] == '+' || oper[0] == '-') )
{
snum.push( atoi(sResult[index].c_str()) );
opnd.push_back(atoi(sResult[index].c_str()));
}
else
{
switch(oper[0])
{
case '+':
{
num1 = snum.top();
Display(opnd, sResult[index]);
std::cout<< num1 << "\t\t" << num1<<" 出OPND栈";
std::cout<< std::endl;
snum.pop();
opnd.pop_back();
num2 = snum.top();
Display(opnd, sResult[index]);
std::cout<< num2 << "\t\t" << num2 <<" 出OPND栈";
std::cout<< std::endl;
snum.pop();
opnd.pop_back();
snum.push( num2 + num1);
opnd.push_back(num2 + num1);
Display(opnd, " ");
std::cout<< "+" << "\t\t" << "计算" << num2 << "+" << num1 << "并将结果压OPND栈";
std::cout<< std::endl;

}
break;
case '-':
{
num1 = snum.top();
Display(opnd, sResult[index]);
std::cout<< num1 << "\t\t" << num1<<" 出OPND栈";
std::cout<< std::endl;
snum.pop();
opnd.pop_back();
num2 = snum.top();
Display(opnd, sResult[index]);
std::cout<< num2 << "\t\t" << num2 <<" 出OPND栈";
std::cout<< std::endl;
snum.pop();
opnd.pop_back();
snum.push( num2 - num1);
opnd.push_back(num2 - num1);
Display(opnd, " ");
std::cout<< "+" << "\t\t" << "计算" << num2 << "-" << num1 << "并将结果压OPND栈";
std::cout<< std::endl;

}
break;
case '*':
{
num1 = snum.top();
Display(opnd, sResult[index]);
std::cout<< num1 << "\t\t" << num1<<" 出OPND栈";
std::cout<< std::endl;
snum.pop();
opnd.pop_back();
num2 = snum.top();
Display(opnd, sResult[index]);
std::cout<< num2 << "\t\t" << num2 <<" 出OPND栈";
std::cout<< std::endl;
snum.pop();
opnd.pop_back();
snum.push( num2 * num1);
opnd.push_back(num2 * num1);
Display(opnd, " ");
std::cout<< "+" << "\t\t" << "计算" << num2 << "*" << num1 << "并将结果压OPND栈";
std::cout<< std::endl;

}
break;
case '/':
{
num1 = snum.top();
Display(opnd, sResult[index]);
std::cout<< num1 << "\t\t" << num1<<" 出OPND栈";
std::cout<< std::endl;
snum.pop();
opnd.pop_back();
num2 = snum.top();
Display(opnd, sResult[index]);
std::cout<< num2 << "\t\t" << num2 <<" 出OPND栈";
std::cout<< std::endl;
snum.pop();
opnd.pop_back();
if(num1 == 0)
{
std::cerr << "Expression worng!" << std::endl;
exit(-1);
}
snum.push( num2 / num1);
opnd.push_back(num2 / num1);
Display(opnd, " ");
std::cout<< "+" << "\t\t" << "计算" << num2 << "*" << num1 << "并将结果压OPND栈";
std::cout<< std::endl;

}
break;
default:
{
snum.push( atoi(sResult[index].c_str()) );
opnd.push_back( atoi(sResult[index].c_str()) );
}
break;
}//swith
}
}//while

int result = snum.top();
snum.pop();
return result;
}

void Expression::Display(const std::vector<int> &opnd, const std::string &soper)
{
size_t index = 0;
for(index; index< opnd.size(); index++)
{
std::cout << opnd[index] << " ";
}
std::cout<< "\t\t" << soper << "\t\t";
}

}//class

int main()
{

std::string Input;

std::cout << "please input the expression (Enter key for end)" << std::endl;
std::getline(std::cin, Input, '\n');

Expression expression;
Expression::Remove_space(Input);
Expression::RPN(Input);

std::cout << std::endl;
std::cout << "后缀表达式:" << std::endl;

for(size_t index = 0; index < Expression::sResult.size(); ++index)
{
std::cout << Expression::sResult[index] << " ";
}

std::cout << std::endl;

std::cout<< Expression::Clculate() << std::endl;
return 0;
}

please input the expression (Enter key for end)
11-(22-11)*2-(-10)+10/5

后缀表达式:
11 22 11 - 2 * - -10 - 10 5 / +
OPND栈 OPTR栈输入字符主要操作
11 22 11 - 11 11 出OPND栈
11 22 - 22 22 出OPND栈
11 11 + 计算22-11并将结果压OPND栈
11 11 2 * 2 2 出OPND栈
11 11 * 11 11 出OPND栈
11 22 + 计算11*2并将结果压OPND栈
11 22 - 22 22 出OPND栈
11 - 11 11 出OPND栈
-11 + 计算11-22并将结果压OPND栈
-11 -10 - -10 -10 出OPND栈
-11 - -11 -11 出OPND栈
-1 + 计算-11--10并将结果压OPND栈
-1 10 5 / 5 5 出OPND栈
-1 10 / 10 10 出OPND栈
-1 2 + 计算10*5并将结果压OPND栈
-1 2 + 2 2 出OPND栈
-1 + -1 -1 出OPND栈
1 + 计算-1+2并将结果压OPND栈
1
Press any key to continu