前言
周五加班的时候,在九度oj上练习了一道简单表达式求值的题目,用到了“算符优先法”,这里简单的记录一下
题目
题目描述:
读入一个只包含 +, -, *, / 的非负整数计算表达式,计算该表达式的值。
输入:
测试输入包含若干测试用例,每个测试用例占一行,每行不超过200个字符,整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束,相应的结果不要输出。
输出:
对每个测试用例输出1行,即该表达式的值,精确到小数点后2位。
样例输入:
1 + 2
4 + 2 * 5 - 7 / 11
0
样例输出:
3.00
13.36
思路
对表达式 4 + 2 × 5 - 7 / 11进行计算,需要了解算法四则运算的规则,即:
1.先乘除,后加减
2.从左到右计算
实现算法
(1)为了实现算符优先法,可以使用两个工作栈。一个称作OPTR,用以寄存运算符;另一个称为OPRD,用以寄存操作数或者运算结果。
(2)初始化两个栈,并且置栈空。(假设表达式是没有语法错误的)
(3)依次读入表达式中每个字符,若是操作数则进OPTD栈,若是运算符,则和OPTR栈的栈顶运算符比较优先权后作相应操作,直至整个表达式求值完毕(即表达式指针到了最后一个字符并且OPTR栈为空)
代码实现(c语言顺序栈)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define stacksize 201
struct optr
{
char operator[stacksize];
int top;
};
struct optd
{
double data[stacksize];
int top;
};
void initStackOptr(struct optr *);
void initStackOptd(struct optd *);
void pushStackOptr(struct optr *, char );
void pushStackOptd(struct optd *, double );
char getStackOptrTop(struct optr *);
int compareOperator(char, char);
char popStackOptr(struct optr *);
double popStackOptd(struct optd *);
double calculateData(double, double, char);
int main()
{
struct optr *optr;
struct optd *optd;
int i, len;
double sum, x, data1, data2;
char string[201], opt, opt1, opt2;
while(gets(string) && string[0] != '0')
{
//初始化栈、表达式长度
len = strlen(string);
optr = (struct optr *)malloc(sizeof(struct optr));
optd = (struct optd *)malloc(sizeof(struct optd));
if(optr == NULL || optd == NULL)
{
exit(EXIT_FAILURE);
}
initStackOptr(optr);
initStackOptd(optd);
//计算表达式的值,使用“算符优先法”
for(i = 0; i < len; i ++)
{
if(string[i] != ' ')
{
if(string[i] >= '0' && string[i] <= '9')
{
x = string[i] - '0';
while(string[i + 1] >= '0' && string[i + 1] <= '9')
{
x = 10 * x + (string[i + 1] - '0');
i ++;
}
//操作数进栈
pushStackOptd(optd, x);
}else
{
//获取栈顶运算符
opt = getStackOptrTop(optr);
switch(compareOperator(opt, string[i]))
{
case 0:
//栈顶优先级低
pushStackOptr(optr, string[i]);
break;
case 1:
//栈顶优先级高
opt = popStackOptr(optr);
data1 = popStackOptd(optd);
data2 = popStackOptd(optd);
sum = calculateData(data1, data2, opt);
pushStackOptd(optd, sum);
i --;
break;
}
}
}
}
//判断算符栈是否为空
while(optr -> top != 0)
{
opt = popStackOptr(optr);
data1 = popStackOptd(optd);
data2 = popStackOptd(optd);
sum = calculateData(data1, data2, opt);
pushStackOptd(optd, sum);
}
//输出计算结果
printf("%.2lf\n",sum);
}
return 0;
}
void initStackOptr(struct optr *s)
{
s->top == 0;
}
void initStackOptd(struct optd *s)
{
s->top == 0;
}
void pushStackOptr(struct optr *s, char opt)
{
//判断栈满
if(s->top - 1 == stacksize)
{
exit(EXIT_FAILURE);
}
s->operator[s->top ++] = opt;
}
void pushStackOptd(struct optd *s, double x)
{
//判断栈满
if(s->top - 1 == stacksize)
{
exit(EXIT_FAILURE);
}
s->data[s->top ++] = x;
}
char getStackOptrTop(struct optr *s)
{
//判断栈空
if(s->top == 0)
{
return '#';
}
return s->operator[s->top - 1];
}
int compareOperator(char opt1, char opt2)
{
//默认opt1优先级高,opt2优先级高返回0
int flag = 1;
if(((opt1 == '+' || opt1 == '-') && (opt2 == '*' || opt2 == '/')) || opt1 == '#')
{
flag = 0;
}
return flag;
}
char popStackOptr(struct optr *s)
{
//判断栈空
if(s->top == 0)
{
exit(EXIT_FAILURE);
}
return s->operator[-- s->top];
}
double popStackOptd(struct optd *s)
{
//判断栈空
if(s->top == 0)
{
exit(EXIT_FAILURE);
}
return s->data[-- s->top];
}
double calculateData(double data1, double data2, char operator)
{
switch(operator)
{
case '+':
return data2 + data1;
case '-':
return data2 - data1;
case '*':
return data2 * data1;
case '/':
if(data1 == 0)
{
exit(EXIT_FAILURE);
}
return data2 / data1;
}
}
大家可以参考一下,好了,下一篇博客可能就是openvpn的搭建了,有需要的同学可以关注,工作需要记录一下搭建过程吧
分享到:
相关推荐
用算符优先分析方法设计一个分析解释程序,对输入的赋值语句、输出语句、清除语句进行词法分析、语法分析、表达式求值并存储于指定变量中;若存在错误,提示错误相关信息。
(Python实现,注释详细)直接输入:3+4*5,一般的...(1)第一阶段,运用算符优先分析算法完成计算器中对算术表达式的语法分析; (2)第二阶段,设计属性文法,改造第一阶段的程序,完成算术表达式的计算和相关的输出。
设计一个程序,演示用算符优先法对算术表达式求值的过程。 【基本要求】 以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用运算符优先关系,实现对算术四则混合运算表达式的求值。 【测试数据】 ...
数据结构 课程设计 表达式求值
大二下半学期数据结构课程设计——算术表达式求值是实现程序设计语言的基本问题之一,也是栈的应用的一个典型例子。设计一个程序,演示用算符优先法对算术表达式求值的过程。
输入——表达式;; 输出——表达式语法是否正确; 四、设计概要 (一)语法分析器设计 1.算术表达式文法 G(E): E E ω0 T | T T T ω1 F | F F i | (E) 2.文法变换: G’(E) : ETe e+Te|ε T...
东北大学2022编译原理实验课——递归下降分析简单算术表达式(C++) 【问题描述】 1.设计简单算数表达式语法分析器算法;(用递归下降分析来实现) 2.编写代码并上机调试运行通过。 【输入形式】 简单算数表达式 ...
《编译》——复习资料,可适用于课程学习资料、期末复习资料、自主学习资料等等,复习资料共218页,内容丰富,干货十足! 主要内容包括: 一、概述 1 1.1 课程介绍 1 1.2 编译过程 3 1.3 高级语言程序简介 11 二、...
5.2.1算符优先文法及优先表构造 5.2.2算符优先分析算法 5.2.3优先函数 5.2.4算符优先分析中的出错处理 5.3LR分析法 5.3.1 LR分析器 5.3.2LR(O)项目集族和LR(O)分析表的构造 5.3.3 SLR分析表的构造 ...
5.2 算符优先分析 5.3 LR分析法 5.4 语法分析器的自动产生工具YACC 第六章 属性文法和语法制导翻译 6.1 属性文法 6.2 基于属性文法的处理方法 6.3 S-属性文法的自下而上计算 6.4 L-属性文法和自顶向下...