[问题描述]
一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正实数，运算符只含加减乘除等四种运算符，界限符只含左右括号如：6+15*（21-8/4）。编程利用“运算符优先法”求算术表达式的值。
[基本要求]
（1）读入一个合法的算术表达式，输出正确的结果。
（2）考虑算法的健壮性，当表达式错误时，要给出错误原因的提示。
（4）实现非整数的处理。
1、判断算术表达式是否正确
2、求出运算结果
我们平常写出的算式对于我们来说是比较直观和容易计算的，这种形式的表达式被称为中缀表达式，但对于计算机而言，中缀表达式是无法直接进行计算的。因为在计算过程中，我们不是读到一个运算符就立即计算，而是要与后面的运算符进行优先级比较，以决定先算哪个，而计算机却做不到这点，但我们可以栈来解决这个问题。具体实现方法如下：
首先，我们创建两个栈 Num 和 Sign ，Num 保存运算数，Sign 保存运算符号。然后，我们依次读取表达式中的字符，若为运算数，则转化为对应数值压入 Num栈中；若为运算符，则和 Sign栈的栈顶运算符进行优先级比较：若栈顶运算符优先级低于当前运算符，则将当前运算符压入Sign栈中；若栈顶运算符优先级高于当前运算符，则 Sign栈弹出运算符、Num栈弹出两个运算数，进行相应计算，并将计算结果压入 Num栈中；但若为 ‘)’ ，则需要将对应左括号从 Sign栈中弹出，这就需要完成两个括号内的所有运算，计算方式同上。直到表达式遍历完毕，Num栈的栈顶元素即为最终结果。
算法思想如此，实现起来却并不简单。例如，我们要将运算数转化为对应数值，由于包括浮点数的情况，这个实现起来就比较复杂。以下是我的程序代码：
# include <iostream>
# include <algorithm>
# include <string>
# include <stack>
using namespace std;
bool CheckOperator(char c); //判断是否为运算符
bool CheckMatch(string str); //判断算式是否正确
int Prior(char c); //求符号的优先级
bool CheckPrior(char c1, char c2); //通过优先级判断是否入栈
float CalNum(float a, float b, char c); //求单项运算的结果
float CalResult(string str); //计算最终结果
int main()
{
string str;
cout << "请输入计算式:";
cin >> str;
str.append("#"); //作为算式的终止符
bool t = CheckMatch(str); //判断算式是否正确
if (t) {
float r = CalResult(str); //计算最终结果
cout << "计算结果为:" << r << endl;
}
return 0;
}
bool CheckOperator(char c) //判断是否为运算符
{
if (c == '+' || c == '-' || c == '*' || c == '/') {
return true;
}
else {
return false;
}
}
bool CheckMatch(string str) //判断算式是否正确
{
if (CheckOperator(str[0]) || CheckOperator(str[str.length() - 2])) {
//算式首尾位置出现运算符
cout << "算术表达式错误！\n" << "原因：缺少用于运算的数" << endl;
return false;
}
//判断括号及运算符输入是否正确
stack<char>S; //用于存放括号的栈
for (int i = 0; i < str.length() - 1; i++) {
if (!CheckOperator(str[i]) && (str[i] < 48 || str[i]>57) && str[i] != '(' && str[i] != ')' && str[i] != '.') {
//出现非法字符
cout << "算术表达式错误！\n" << "原因：出现非法字符" << str[i] << endl;
return false;
}
if (CheckOperator(str[i]) && CheckOperator(str[i + 1])) {
//运算符重复
cout << "算术表达式错误！\n" << "原因：运算符" << str[i] << "重复" << endl;
return false;
}
if (str[i] == '(')
{
S.push(str[i]);
if (CheckOperator(str[i + 1])) {
//'('后缺少用于运算的数
cout << "算术表达式错误！\n" << "原因：缺少用于运算的数" << endl;
return false;
}
}
if (str[i] == ')')
{
if (S.empty()) {
//若栈已为空，说明遗漏左括号
cout << "算术表达式错误！\n" << "原因：遗漏左括号" << endl;
return false;
}
S.pop();
}
}
if (!S.empty()) {
//若此时栈还不为空，说明遗漏右括号
cout << "算术表达式错误！\n" << "原因：遗漏右括号" << endl;
return false;
}
return true;
}
int Prior(char c) //返回符号的优先级
{
switch (c)
{
case '#': return 0;
case '+':
case '-': return 1;
case '*':
case '/': return 2;
case ')': return 3;
case '(': return 4;
}
}
bool CheckPrior(char c1, char c2) //通过优先级判断是否入栈（c1当前，c2栈中）
{
if (c2 == '(') {
return true; //同意进栈
}
int p1 = Prior(c1);
int p2 = Prior(c2);
if (p1 > p2) { //当前运算符的优先级较高
return true; //同意进栈
}
else {
return false; //不同意进栈
}
}
float CalNum(float a, float b, char c) //求单项运算的结果
{
switch (c)
{
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
}
}
float CalResult(string str) //计算最终结果
{
stack<float>Num; //保存运算数的栈
stack<char>Sign; //保存运算符的栈
Sign.push('#');
float a, b;
for (int i = 0; i < str.length() && !Sign.empty(); i++) {
if (str[i] >= 48 && str[i] <= 57) {
//若为数字
a = float(str[i]) - 48; //a保存由字符转化为数字后的值
int j;
//将字符转化为数字
for (j = i + 1; (str[j] == '.') || (j < str.length() && str[j] >= 48 && str[j] <= 57); j++) {
if (str[j] == '.') {
//若为小数
int k, l;
for (k = j + 1, l = 1; k < str.length() && str[k] >= 48 && str[k] <= 57; k++, l++) {
b = float(str[k]) - 48;
a = a + b * pow(10, -l);
}
j = k;
break;
}
else {
b = float(str[j]) - 48;
a = a * 10 + b;
}
}
i = j - 1;
Num.push(a); //运算数进栈
}
else {
//若为运算符
char c1 = str[i]; //c1当前运算符
while (1) {
char c2 = Sign.top(); //c2栈顶运算符
if (c2 == '#' && str[i] == '#') { //若遇到起始符，并且str也到达末尾
Sign.pop();
break;
}
bool t = CheckPrior(c1, c2); //通过优先级判断是否入栈（c1当前，c2栈中）
if (t) {
//同意运算符进栈
int s = Prior(str[i]);
if (s == 3) {
//出现')'，优先进行括号内的运算
while ((c2 = Sign.top()) != '(') {
a = Num.top(); //取出第一个数
Num.pop();
b = Num.top(); //取出第二个数
Num.pop();
float r = CalNum(b, a, c2); //求单项运算的结果
Sign.pop();
Num.push(r); //运算得到的新数进栈
}
Sign.pop();
}
else {
Sign.push(c1); //运算符进栈
}
break;
}
else {
//不同意运算符进栈，执行运算操作
a = Num.top();
Num.pop();
b = Num.top();
Num.pop();
float r = CalNum(b, a, c2); //求单项运算的结果
Sign.pop();
Num.push(r);
}
}
}
}
return Num.top();
}
运行结果：
请输入计算式:((1+2*3)-1)/2+1.5*3
计算结果为:7.5请输入计算式:(1+3)*4)-2
算术表达式错误！
原因：遗漏左括号总结：实现简易计算器主要运用了栈的数据结构。其中主要的操作是通过遍历算数表达式实现的，所以程序总的时间复杂度约为O(n)，n是指算数表达式的长度。对于正在练习栈的小伙伴们来说，简易计算器是很不错的练习项目。文章来源：https://www.toymoban.com/news/detail-718742.html
以上是我个人的学习成果，很高兴能与大家分享。文章来源地址https://www.toymoban.com/news/detail-718742.html
到了这里，关于简易计算器（详解用栈实现算术表达式求值）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
