今天有师妹求助,要实现带有括号、加减乘除、阶乘的表达式计算
一时冲动便给师妹写了一下,C语言代码如下,用了两个栈来实现逆波兰表达式求值:
//作者:卞昊穹
//邮箱:bianhaoqiong(AT)163.com
//2012.04.26
//欢迎参考,引用请注明原作者
#include <stdio.h>
#include <stdlib.h>
//运算符栈的长度
#define OPSTACK_LENGTH 5
//操作数栈的长度
#define NUMSTACK_LENGTH 100
//输入串的最大长度
#define MAX_STRING_LENGTH 100
//运算符结构体
struct operatorStruct
{
//运算符名称
char name;
//优先级
int priority;
//目数,即操作数个数,例如单目运算符为1,双目运算符2
int opnum;
};
typedef struct operatorStruct OPERATOR;
//运算符栈
OPERATOR opStack[OPSTACK_LENGTH];
//运算符栈顶指针
int opStackTop = -1;
//操作数栈
double numStack[NUMSTACK_LENGTH];
//操作数栈顶指针
int numStackTop = -1;
//获取一个字符所代表的运算符的优先级
int getPriority(char name)
{
if (name == '(' || name == ')')
{
return 0;
}
if (name == '!')
{
return 3;
}
if (name == '*' || name == '/')
{
return 2;
}
if (name == '+' || name == '-')
{
return 1;
}
exit(1);
}
//获取一个字符所代表的运算符的目数
int getOpNum(char name)
{
if (name == '*' || name == '/' || name == '+' || name == '-')
{
return 2;
}
if (name == '!')
{
return 1;
}
if (name == '(' || name == ')')
{
return 0;
}
exit(1);
}
//运算符压栈
void pushOperator(OPERATOR op)
{
if (opStackTop < OPSTACK_LENGTH - 1)
{
opStack[++opStackTop] = op;
}
else
{
exit(1);
}
}
//运算符出栈
OPERATOR popOperator()
{
if (opStackTop >= 0)
{
return opStack[opStackTop--];
}
else
{
exit(1);
}
}
//操作数压栈
void pushNumber(double num)
{
if (numStackTop < NUMSTACK_LENGTH - 1)
{
numStack[++numStackTop] = num;
}
else
{
exit(1);
}
}
//操作数出栈
double popNumber()
{
if (numStackTop >= 0)
{
return numStack[numStackTop--];
}
else
{
exit(1);
}
}
//将输入字符串中的以0-9开头、到下一个运算符结束的一段转化为浮点型
//i加上浮点型对应的字符串的长度
double getNumFromString(char *s, int *i)
{
int j = 0;
static char numstr[MAX_STRING_LENGTH];
while ((*s) >= '0' && *s <= '9')
{
numstr[j++] = (*s);
s++;
}
if ((*s) == '.')
{
numstr[j++] = (*s);
s++;
while ((*s) >= '0' && *s <= '9')
{
numstr[j++] = (*s);
s++;
}
}
(*i) = (*i) + j;
numstr[j] = '\0';
return atof(numstr);
}
//从操作数栈中弹出两个操作数,完成一次双目运算
double opertate2Num(OPERATOR op)
{
double num2 = popNumber();
double num1 = popNumber();
if (op.name == '+')
{
return num1 + num2;
}
if (op.name == '-')
{
return num1 - num2;
}
if (op.name == '*')
{
return num1 * num2;
}
if (op.name == '/')
{
return num1 / num2;
}
exit(1);
}
//从操作数栈中弹出一个操作数,完成一次单目运算
double opertate1Num(OPERATOR op)
{
double num = popNumber();
if (op.name == '!')
{
double result = 1;
while (num > 1)
{
result *= num;
num--;
}
return result;
}
exit(1);
}
//完成一次运算
double operate(OPERATOR op)
{
if (op.opnum == 1)
{
return opertate1Num(op);
}
else if (op.opnum == 2)
{
return opertate2Num(op);
}
exit(1);
}
int main()
{
char string[MAX_STRING_LENGTH];//表达式的输入串
int i;
OPERATOR op, topOp;//op为从当前输入串中提取的一个运算符,topOp为运算符栈栈顶的运算符
topOp.name = '#';
topOp.priority = 0;
topOp.opnum = 0;
pushOperator(topOp);//压入#作为初始运算符
scanf("%s", string);
for (i = 0; string[i] != '\0' && string[i] != '=';)
{
//从输入串中取出一个字符作为开始,进行处理,直到表达式结束
if (string[i] >= '0' && string[i] <= '9')
{
//如果是操作数,将整个操作数提取出来,压入操作数栈
pushNumber(getNumFromString(&string[i], &i));
}
else
{
op.name = string[i];
op.priority = getPriority(string[i]);
op.opnum = getOpNum(string[i]);
topOp = popOperator();
if (op.name == '(')
{
//如果是'(',将从栈顶弹出的运算符压回栈内,并将当前运算符则压栈
pushOperator(topOp);
pushOperator(op);
}
else if (op.name == ')')
{
//如果是')',则进行运算,每次运算结果作为一个操作数压入操作数栈,直到将'('弹出运算符栈
while (topOp.name != '(')
{
pushNumber(operate(topOp));
topOp = popOperator();
}
}
else
{
//如果是普通运算符
if (topOp.name != '#' && op.priority <= topOp.priority)
{
//如果运算符栈非空,且当前运算符的优先级大于栈顶运算符,则进行一次运算,将结果压入操作数栈
pushNumber(operate(topOp));
}
else
{
//否则将从栈顶弹出的运算符压回
pushOperator(topOp);
}
//将当前运算符压栈
pushOperator(op);
}
i++;
}
}
//完成栈内剩余的运算
while ((topOp = popOperator()).name != '#')
{
pushNumber(operate(topOp));
}
//操作数栈中剩下的最后一个数即为结果
printf("%f\n", popNumber());
return 0;
}
分享到:
相关推荐
C语言之逆波兰表达式完整代码(附算法),详细讲解其实现
是个人上数据结构课后,通过4天努力写出的代码文章,可能不是很好,但可用来参考参考!
基于c语言的将算术中缀表达式转化为逆波兰表达式,注释清晰且代码打头有写好的思想。
使用c语言实现,将给定的运算表达式翻译成逆波兰表达式的形式
表达式求值,逆波兰表达式算法,支持任何位数值运算,运算符支持+-*/(),其它运算符请自行扩展,代码比较松耦合可扩展性好
本文主要对Java算法逆波兰表达式的相关内容作了介绍,涉及逆波兰表达式的定义已经在Java中的实现,具有一定参考价值,需要的朋友可以了解下。
表达式求值 逆波兰表达式算法,支持任何位数值运算,运算符支持+-*/(),其它运算符请自行扩展,代码比较松耦合可扩展性好
本代码可简单实现中缀表达式转换为逆波兰表达式,设计的栈底字符为#号,输入串默认尾部追加#号,没有单独将非运算符归入各自的栈,只是输出成一个逆波兰表达式的字符串。比较简单,如有错误之处,望您评论指出。
简易灰色逆波兰表达式计算器代码,一款适用于手机移动端的网页计算器。
这是我的一个小程序,请大家批评指教,谢谢大家的支持!!
易语言逆波兰表达式计算源码,逆波兰表达式计算,匹配_括号匹配,文本_逐字分割_取代码,获取优先级,求后续表达式,计算
源代码 博文链接:https://leon-a.iteye.com/blog/186104
学习YACC(BISON)的语法结构,编写YACC(BISON)程序,生成能够分析和计算逆波兰表达式,构建逆波兰计算器。根据提示,在右侧编辑器补充代码,实现加法(+)、减法(-)、乘法(*)、除法(/)、乘方(^)以及取负运算(n)。
逆波兰表达式求值 题目 根据逆波兰表示法,求表达式的值。 有效的运算符包括 + ,- ,* ,/ 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。 链接:...
本文实例为大家分享了C++实现逆波兰表达式的具体代码,供大家参考,具体内容如下 当我们输入一个数学表达式,是中缀表达式,我们首先转换为后缀表达式(逆波兰表达式),然后再进行求值。 在《大话数据结构》的104-...
使用C++模拟了计算器的四则运算,包括加减乘除以及括号优先级运算,主要解决办法是将键盘输入的四则运算表达式转为逆波兰表达式,然后再进一步计算逆波兰表达式的值,具体算法思路在主页,资源包括一个main.cpp文件...
(1)建立两个栈,一个S1用来存放操作符+ - * / ( ),另一个S2用来存放生成的逆波兰表达式(本文中为了方便用一个字符串来存放逆波兰表达式),操作符栈遵循越往栈顶操作符优先级越高的原则。 (2)从中缀表达式的...
中缀表达式转逆波兰表达式的增强版,给要学习数据结构的同学们参考,程序代码易懂
用C写的一个算24点代码,使用逆波兰表达式的求值.zip