昨天晚上沒事,把《數據結構》書拿出來看，在堆棧那一章里面，講到使用堆棧來實現表達式求值。步驟是先將表達式轉換為后綴表達式，在對后綴表達式處理。
今天在公司沒事，也寫了個表達式計算。不需要轉換成后綴，可以直接計算。大概的算法是：生成兩個棧，一個是用來存放數值，一個用來放操作符。如果操作符大于棧頂符號的優先值，則取出數值和操作符進行計算。將計算的結果放到數值棧中。如果是‘）’，則要計算直到符號棧中為‘（’。好象講的不清楚，還是看程序。
#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();
};