逆波兰法求解数学表达示(C++)

主要是栈的应用,里面有两个函数deleteSpace(),stringToDouble()在我还有一篇博客其中:对string的一些扩展函数。

本程序仅仅是主要的功能实现,没有差错控制。

#include<iostream>
#include<stack>
#include<string>
#include<map>
#include"fstring.h" /*
*採用逆波兰表示法求解数学表达示
*1、将输入的中缀表示示转换成后缀表达示
*2、将后缀表达示进行计算得出结果
*/
using namespace std; stack<string> postOrderStr;
map<string, int> symbolPriority;
void initializationSymbol(map<string, int>& symbol)
{//定义优先级
pair<string, int> element;
element = make_pair("+", 0);
symbol.insert(element); element = make_pair("-", 0);
symbol.insert(element); element = make_pair("*", 1);
symbol.insert(element); element = make_pair("/", 1);
symbol.insert(element);
} void strToPostStack(string& str, stack<string>& postOrderStr)
{//首先将输入的数学表达示表示成后缀表达示
stack<string> auxilary;//辅助数组。用于暂时存放符号
string::iterator iter = str.begin();
string::iterator iter1 = iter;
bool flag = false;//是否遇到括号
for (; iter != str.end(); ++iter)
{
if (*iter == '+' || *iter == '-' || *iter == '*' || *iter == '/' || *iter == '(' || *iter == ')')
{
if (iter1 != iter)
{//可能会出现两个连续的符号
string subStr(iter1, iter);
//存入数字
postOrderStr.push(subStr);
}
string symbol(iter,iter+1);//符号 //按优先级存入符号。
if (*iter == '(')
{
flag = true;
auxilary.push(symbol);
}
else if (flag && *iter != ')')
{
auxilary.push(symbol);
}
else if (!flag)
{
if (auxilary.empty())
{
auxilary.push(symbol);
}
else
{
string tmp2 = auxilary.top();
while (symbolPriority[tmp2] >= symbolPriority[symbol])
{
postOrderStr.push(tmp2);
auxilary.pop();
if (auxilary.empty())
break;
tmp2 = auxilary.top();
}
auxilary.push(symbol);
}
}
else if (flag && *iter == ')')
{
string tmp1 = auxilary.top();
do{
postOrderStr.push(tmp1);
auxilary.pop();
tmp1 = auxilary.top();
} while (tmp1!="(");
auxilary.pop();
flag = false;
} //存放下一个数字起始位置
iter1 = iter+1;
}
}
string tmp5(iter1, iter);
postOrderStr.push(tmp5);
while (!auxilary.empty())
{
string tmp6 = auxilary.top();
postOrderStr.push(tmp6);
auxilary.pop();
}
} double computeFun(stack<string> postOrderStrNew)
{//溢出控制
stack<double> computeStack;//计算辅助栈
while (!postOrderStrNew.empty())
{
string tmp7 = postOrderStrNew.top();
if (tmp7 == "+" || tmp7 == "-" || tmp7 == "*" || tmp7 == "/")
{//遇到符号则取出计算辅助栈中的两个元素開始计算,并将结果压入栈中
double value1, value2, value3;
value1 = computeStack.top();
computeStack.pop();
value2 = computeStack.top();
computeStack.pop();
if (tmp7 == "+")
{
value3 = value2 + value1;
}
else if (tmp7 == "-")
{
value3 = value2 - value1;
}
else if (tmp7 == "*")
{
value3 = value2 * value1;
}
else
{
value3 = value2 / value1;
}
computeStack.push(value3);
}
else
{
double value;
//把字符转换成数值,然后压入栈中
value = stringToDouble(tmp7);
computeStack.push(value);
}
postOrderStrNew.pop();
}
return computeStack.top();
} int main()
{
initializationSymbol(symbolPriority);
string mathStr;
cout << "Please input a math string:"<<endl;
getline(cin,mathStr);
cout << "The string you input is:" << endl;
deleteSpace(mathStr);
cout << mathStr<<endl;
strToPostStack(mathStr, postOrderStr);
stack<string> postOrderStrNew;
while (!postOrderStr.empty())
{
string tmp4 = postOrderStr.top();
//cout << tmp4 << " ";
//转存到还有一个栈中就是后缀表达示了
postOrderStrNew.push(tmp4);
postOrderStr.pop();
}
cout << endl;
cout << "The compute result is:"<<computeFun(postOrderStrNew)<<endl;
return 0;
}
上一篇:接口的作用(C#)


下一篇:《JS权威指南学习总结--6.3删除属性》