大家好,又见面了,我是你们的朋友全栈君。
为了实现用栈计算算数表达式的值,需设置两个工作栈:用于存储运算符的栈opter,以及用于存储操作数及中间结果的栈opval。
算法基本思想如下:
(1)首先将操作数栈opval设为空栈,而将’#’作为运算符栈opter的栈底元素,这样的目的是判断表达式是否求值完毕。
(2)依次读入表达式的每个字符,表达式须以’#’结尾,若是操作数则入栈opval,若是运算符,则将此运算符c与opter的栈顶元素top比较优先级后执行相应的操作,(具体操作如下:(i)若top的优先级小于c,即top<c,则将c直接入栈opter,并读入下一字符赋值给c;(ii)若top的优先级等于c,即top=c,则弹出opter的栈顶元素,并读入下一字符赋值给c,这一步目的是进行括号操作;(iii)若top优先级高于c,即top>c,则表明可以计算,此时弹出opval的栈顶两个元素,并且弹出opter栈顶的的运算符,计算后将结果放入占opval中。)直至opter的栈顶元素和当前读入的字符均为’#’,此时求值结束。
算符间的优先关系如下表所示:
表中需要注意的是θ1为opter的栈顶元素,θ2位从表达式中读取的操作符,此优先级表可以用二维数组实现,具体见代码(表来源:严蔚敏《数据结构》)。
具体代码如下:
#include<iostream> //输入的表达式要以'#'结尾,如‘5+6*3/(3-1)#’
#include<cstring>
#include<cstdio>
#include<cctype>
#include<stack>
using namespace std;
stack<char> opter; //运算符栈
stack<double> opval; //操作数栈
int getIndex(char theta) //获取theta所对应的索引
{
int index = 0;
switch (theta)
{
case '+':
index = 0;
break;
case '-':
index = 1;
break;
case '*':
index = 2;
break;
case '/':
index = 3;
break;
case '(':
index = 4;
break;
case ')':
index = 5;
break;
case '#':
index = 6;
default:break;
}
return index;
}
char getPriority(char theta1, char theta2) //获取theta1与theta2之间的优先级
{
const char priority[][7] = //算符间的优先级关系
{
{ '>','>','<','<','<','>','>' },
{ '>','>','<','<','<','>','>' },
{ '>','>','>','>','<','>','>' },
{ '>','>','>','>','<','>','>' },
{ '<','<','<','<','<','=','0' },
{ '>','>','>','>','0','>','>' },
{ '<','<','<','<','<','0','=' },
};
int index1 = getIndex(theta1);
int index2 = getIndex(theta2);
return priority[index1][index2];
}
double calculate(double b, char theta, double a) //计算b theta a
{
switch (theta)
{
case '+':
return b + a;
case '-':
return b - a;
case '*':
return b * a;
case '/':
return b / a;
default:
break;
}
}
double getAnswer() //表达式求值
{
opter.push('#'); //首先将'#'入栈opter
int counter = 0; //添加变量counter表示有多少个数字相继入栈,实现多位数的四则运算
char c = getchar();
while (c != '#' || opter.top() != '#') //终止条件
{
if (isdigit(c)) //如果c在'0'~'9'之间
{
if (counter == 1) //counter==1表示上一字符也是数字,所以要合并,比如12*12,要算12,而不是单独的1和2
{
double t = opval.top();
opval.pop();
opval.push(t * 10 + (c - '0'));
counter = 1;
}
else
{
opval.push(c - '0'); //将c对应的数值入栈opval
counter++;
}
c = getchar();
}
else
{
counter = 0; //counter置零
switch (getPriority(opter.top(), c)) //获取运算符栈opter栈顶元素与c之间的优先级,用'>','<','='表示
{
case '<': //<则将c入栈opter
opter.push(c);
c = getchar();
break;
case '=': //=将opter栈顶元素弹出,用于括号的处理
opter.pop();
c = getchar();
break;
case '>': //>则计算
char theta = opter.top();
opter.pop();
double a = opval.top();
opval.pop();
double b = opval.top();
opval.pop();
opval.push(calculate(b, theta, a));
}
}
}
return opval.top(); //返回opval栈顶元素的值
}
int main()
{
//freopen("test.txt", "r", stdin);
int t; // 需要计算的表达式的个数
cin >> t;
getchar();
while (t--)
{
while (!opter.empty())opter.pop();
while (!opval.empty())opval.pop();
double ans = getAnswer();
cout << ans << endl<< endl;
getchar();
}
return 0;
}
结果:
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/148806.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...