昨天晚上没事,把《数据结构》书拿出来看，在堆栈那一章里面，讲到使用堆栈来实现表达式求值。步骤是先将表达式转换为后缀表达式，在对后缀表达式处理。
今天在公司没事，也写了个表达式计算。不需要转换成后缀，可以直接计算。大概的算法是：生成两个栈，一个是用来存放数值，一个用来放操作符。如果操作符大于栈顶符号的优先值，则取出数值和操作符进行计算。将计算的结果放到数值栈中。如果是‘）’，则要计算直到符号栈中为‘（’。好象讲的不清楚，还是看程序。
#include "StdAfx.h"
#include ".\calculate.h"
calculate::calculate()
{
//初始化优先級
map_priority['+']=1;
map_priority['-']=1;
map_priority['*']=2;
map_priority['/']=2;
map_priority['(']=3;
map_priority[')']=3;
}
calculate::~calculate(void)
{
}
//開始
void calculate::Run(void)
{
char sign;
double num;
double num1,num2;
cin>>sign;
while(sign!='=')
{
if(isSign(sign)) //sign是符號
{
if(sign==')')
{
//如果是')'操作符，則計算橨直到'('
calculatestack('(');
}
else
{
//比較操作符優先級
//如果操作符大於橨蝢的操作符优先級，則入橨，否則計算.
if(stack_sign.size()==0||get_priority(sign)>get_priority(stack_sign.top()))
{
//操作符入欑
stack_sign.push(sign);
}
else
{
char ch=stack_sign.top();
if(ch!='(')
{
stack_sign.pop();
num2=stack_pop();
num1=stack_pop();
stack_numeral.push(Calculate(num1,num2,ch));//將計算的值重新入橨
}
stack_sign.push(sign);
}
}
}
else
{
cin.putback(sign);
cin>>num;
stack_numeral.push(num);
}
cin>>sign;
}
//計算橨內剩余操作符
calculatestack();
cout<<stack_numeral.top()<<endl;
system("PAUSE");
}
//是否是操作符
bool calculate::isSign(char sign)
{
if(map_priority.find(sign)==map_priority.end())
return false;
else
return true;
}
// 优先級大小
int calculate::get_priority(char sign)
{
return map_priority[sign];
}
double calculate::Calculate(double &num1,double &num2,char & sign)
{
double temp;
switch(sign)
{
case '+':
temp=num1+num2;
break;
case '-':
temp=num1-num2;
break;
case '*':
temp=num1*num2;
break;
case '/':
temp=num1/num2;
break;
}
return temp;
}
//計算橨直到操作符是sign
void calculate::calculatestack(char sign)
{
char ch;
double num1,num2;
ch=stack_sign.top();
stack_sign.pop();
while(ch!=sign)
{
num2=stack_pop();
num1=stack_pop();
stack_numeral.push(Calculate(num1,num2,ch));//將計算的值重新入橨
if(stack_sign.size()==0) //如果為空
break;
ch=stack_sign.top();
stack_sign.pop();
}
}
//數值出橨
double calculate::stack_pop()
{
double n;
if(stack_numeral.size()==0)
return 0;
else
n=stack_numeral.top();
stack_numeral.pop();
return n;
}文件头
#pragma once
#include <string>
#include <stack>
#include <map>
using namespace std;
class calculate
{
public:
calculate(void);
~calculate(void);
private:
stack<double> stack_numeral;
stack<char> stack_sign;
map<char,int> map_priority;
public:
void Run(void);
private:
bool isSign(char);
// 优先級大小
int get_priority(char sign);
double Calculate(double &num1,double &num2,char & sign);
void calculatestack(char sign=' ');
double stack_pop();
};