数据结构--栈的应用-表达式求值算法C++(模板类实现)
作者:
AmbitionX
,
2022-05-04 15:14:04
,
所有人可见
,
阅读 241
#include <iostream>
#include <cstring>
using namespace std;
const int Size = 100;
class Expression
{
public:
Expression(string str);
// ~Expression(); // 静态存储为空
int Compute(); // 计算表达式str的值
private:
int Comp(char str1, char str2); // 比较str1和str2的优先级
string str;
};
Expression :: Expression(string str)
{
this->str = str + "#"; // 接收键盘输入并加上界定符
}
// Expression :: ~Expression(){}
int Expression :: Compute()
{
char OPND[Size], OPTR[Size]; // 定义两个数组相当于两个栈 一个存符号,一个存数值
OPTR[0] = '#'; // 符号栈初始化一个界定符号
int top1 = -1, top2 = 0;
int k, x, y, z, op;
for (int i = 0; str[i] != '\0'; ) //依次扫描
{
if (str[i] >= 48 && str[i] <= 57) // 数字的ASCII区间
OPND[++ top1] = str[i ++] - 48; // 将字符转换为数字
else
{
k = Comp(str[i], OPTR[top2]);
if (k == 1) OPTR[++ top2] = str[i++]; // 将str[i]压入运算符栈
else if (k == -1)
{
// 取出两个元素
y = OPND[top1 --];
x = OPND[top1 --];
// 取出一个符号
op = OPTR[top2 --];
switch (op)
{
case '+' : z = x + y; break;
case '-' : z = x - y; break;
case '*' : z = x * y; break;
case '/' : z = x / y; break;
default : break;
}
OPND[++ top1] = z; // 运算结果压入对象栈
}
else // str[i]与运算栈的栈顶元素优先级相同
{
// 匹配str[i],扫描下一个字符
top2 --;
i++;
}
}
}
return OPND[top1]; // 运算对象栈的栈顶元素为结果
}
int Expression :: Comp(char str1, char str2)
{
// 比较str1和str2的优先级, 1表示str1的高, 0表示相同, -1表示str1的低
switch (str1)
{
case '+' :
case '-' : if (str2 == '(' || str2 == '#') return 1; else return -1; break;
case '*' :
case '/' : if (str2 == '*' || str2 == '/') return -1; else return 1; break;
case '(' : return 1; break;
case ')' : if (str2 == '(') return 0; else return -1; break;
case '#' : if (str2 == '#') return 0; else return -1; break;
default : break;
}
}
int main()
{
string str;
cout << "请输入一个表达式: " << endl;
cin >> str;
Expression E{str}; // 定义对象变量E
int result = E.Compute(); // 结果
cout << "表达式的结果是: " << result << endl;
return 0;
}