#include <iostream>
using std::cin;
using std::cout;
using std::endl;
template<typename T>
class Stack
{
public:
Stack(int _size = 20) :size(_size), mtop(0)
{
data = new T[size]();
}
~Stack()
{
delete[] data;
}
/* 判空 */
bool empty()
{
return mtop == 0;
}
void push(int val)
{
if (Full())
{
throw std::exception("error: Stack is Full !");
}
data[mtop] = val;
mtop++;
}
T top()
{
if (empty())
{
throw std::exception("error: The stack is empty !");
}
return data[mtop - 1];
}
void pop()
{
if (empty())
{
throw std::exception("error: Stack is Empty !");
}
mtop--;
}
void show()
{
if (empty())
{
cout << endl;
}
else
{
int i = 0;
while (i < mtop)
{
cout << data[i] << " ";
i++;
}
cout << endl;
}
}
private:
bool Full()
{
return mtop == size;
}
T* data;
int mtop;
int size;
};
/* 计算器类 */
class Calculator
{
public:
Calculator(int _size = 20):size(_size),result(0)
{
str = new char[_size + 1]();
}
~Calculator()
{
delete[] str;
}
/* 输入 */
void setData()
{
cin.getline(str, size - 1); //最多输入size -1个，末尾加'/0'
}
/* 中缀转后缀 */
void InfixToSuffix(); /* 把str输入的中缀式转换为后缀式 */
/* 后缀计算 */
void Compure();
/* 计算结果 */
double GetResult()
{
return result;
}
private:
bool IsPop(char a, char b);
char* str;
double result;
int size;
};
int main()
{
while (1) {
Calculator ca;
ca.setData();
ca.InfixToSuffix();
ca.Compure();
cout << ca.GetResult() << endl;
}
return 0;
}
bool Calculator::IsPop(char a, char b) //a为待比较符号，b为符号栈栈顶元素
{
if (b == '(') return false;
if (a == '*' || a == '/')
{
if (b == '+' || b == '-')
{
//可以如符号栈
return false;
}
else
{
return true;
}
}
//if (a == '+' || a == '-')
//{
//a符号为最低优先级，符号栈出栈
return true;
//}
}
/* 中缀转后缀 入栈 */
void Calculator::InfixToSuffix()
{
char* des = new char[size]();
/* 符号栈 */
Stack<char> symbol;
int i = 0;
int k = 0;
while (str[i] != ' ')
{
/*----------- 特殊符号判断------------------------------*/
if (str[i] == ' ') //如果当前字符是空格，则往后走一个
{
i++;
continue;
}
else if (str[i] == '(') //左括号直接入栈
{
symbol.push(str[i]);
}
else if (str[i] == ')') //遇到 ） ，输出（ ）之间的所有符号
{
while (symbol.top() != '(')
{
des[k++] = symbol.top();
des[k++] = ' ';
symbol.pop();
}
symbol.pop();
}
/*----------------- 数字 -------------------------------*/
else if (isdigit(str[i]))
{
des[k++] = str[i];
if (!isdigit(str[i + 1])) //数字后加空格
{
des[k++] = ' ';
}
}
/*----------------- 运算符 -------------------------------*/
else
{
switch (str[i])
{
case '+':case '-':case '*':case '/':
if (symbol.empty()) //如果符号栈为空，直接入符号
{
symbol.push(str[i]);
}
else //否则，判断是否选择入符号栈还是出栈顶元素
{
if (IsPop(str[i], symbol.top())) //出符号栈
{
des[k++] = symbol.top();
symbol.pop();
continue;
}
else //当前符号优先级高，入符号栈
{
symbol.push(str[i]);
}
}
break;
default:
break;
}
}
i++; /* 遍历下一字符 */
}
/*字符串已遍历完，把符号栈中剩余的符号入栈到数字栈中 */
while (!symbol.empty())
{
des[k++] = symbol.top();
symbol.pop();
}
des[k] = ' ';
char* tmp = des;
des = str;
str = tmp;
delete[]des;
}
void Calculator::Compure()
{
/* 辅助栈 */
Stack<double> st;
int i = 0;
while (str[i] != ' ')
{
/*----------- 特殊符号判断------------------------------*/
if (str[i] == ' ') //如果当前字符是空格，则往后走一个
{
i++;
continue;
}
/*----------------- 数字 -------------------------------*/
else if (isdigit(str[i]))
{
double tmp = 0;
while (str[i] != ' ')
{
tmp = tmp * 10 + str[i] - '0';
i++;
}
st.push(tmp);
}
/*----------------- 运算符 -------------------------------*/
else if (!st.empty()) //非空
{
double tmp = 0;
switch (str[i])
{
case '+':
tmp += st.top();
st.pop();
tmp += st.top();
st.pop();
st.push(tmp);
break;
case '-':
tmp -= st.top();
st.pop();
tmp += st.top();
st.pop();
st.push(tmp);
break;
case '*':
tmp = st.top();
st.pop();
tmp *= st.top();
st.pop();
st.push(tmp);
break;
case '/':
{
tmp = st.top();
st.pop();
if (tmp != 0)
{
tmp = st.top() / tmp;
st.pop();
st.push(tmp);
}
else
{
throw std::exception("error: Divisor of 0 ！");
}
}
break;
default:
break;
}
}
i++; /* 遍历下一字符 */
}
this->result = st.top();
st.top();
}
运行截图：
