这篇文章主要介绍了 Python 实现调度场算法代码详解, 具有一定参考价值, 需要的朋友可以了解下
调度算法
操作系统管理了系统的有限资源, 当有多个进程 (或多个进程发出的请求) 要使用这些资源时, 因为资源的有限性, 必须按照一定的原则选择进程 (请求) 来占用资源这就是调度目的是控制资源使用者的数量, 选取资源使用者许可占用资源或占用资源
在操作系统中调度是指一种资源分配, 因而调度算法是指: 根据系统的资源分配策略所规定的资源分配算法对于不同的的系统和系统目标, 通常采用不同的调度算法, 例如, 在批处理系统中, 为了照顾为数众多的段作业, 应采用短作业优先的调度算法; 又如在分时系统中, 为了保证系统具有合理的响应时间, 应当采用轮转法进行调度目前存在的多种调度算法中, 有的算法适用于作业调度, 有的算法适用于进程调度; 但也有些调度算法既可以用于作业调度, 也可以用于进程调度
目标阐述:
将中缀表达式转换为后缀表达式(Reverse Polish Notation:RPN 逆波兰式)
参与运算的数据的正则表示为:[0-9]{1,}形式的十进制数
运算符优先级:(从高到低)
( ) 括号
/ * % 除乘余
+ - 加减
解:
第一步: 使用正则词法分析器 flex 生成一个词法分析器, 以处理输入的中缀表达式
从 stdin 接收输入, 检测非法字符, 并将处理后的中缀表达式输出到 stdout
- %option noyywrap
- %{
- #include<stdio.h>
- #include<stdlib.h>%}
- %%
- [0-9]+ { printf("%s",yytext); }
- [()*/% -] { printf("%s",yytext); }
- [[:space:]] {}
- . { printf("\nError\n");exit(1); }
- %%
- int main()
- {
- yylex();
- printf("\n");
- return 0;
- }
第二步: 使用 Python 进行转换
从 stdin 接收一定格式的中缀表达式字符流, 检测是否在词法分析器处理过程中出错, 然后使用调度场算法处理数据, 得到 rpn 列表
- import sys
- line=sys.stdin.readline()
- line2=sys.stdin.readline()
- if len(line2)>0:
- sys.stderr.write("Syntax Error after :")
- sys.stderr.write(line)
- sys.stderr.write("\n")
- exit(1)
- lis=line.split(' ')
- lis.pop()
- lis_old=lis[:]
- lis.reverse()
- oplis=[]
- rpnlis=[]
- str=''arith_op="+-*/%"#'('')' [0-9]+
- prior={ '/':1,'*':1,'%':1, '+':2,'-':2 }
- while len(lis)>0:
- str=lis.pop()
- if str=='(':
- oplis.append('(')
- elif str.isdigit():
- rpnlis.append(str)
- elif len(str)==1 and arith_op.find(str[0])!=-1:
- if len(oplis)==0 or oplis[len(oplis)-1]=='(':
- oplis.append(str)
- else:
- while len(oplis)>0 and oplis[len(oplis)-1]!='(' \
- and prior[oplis[len(oplis)-1]]<=prior[str]:
- rpnlis.append(oplis.pop())
- oplis.append(str)
- elif str==')':
- while len(oplis)>0 and oplis[len(oplis)-1]!='(':
- rpnlis.append(oplis.pop())
- if len(oplis)>0:
- oplis.pop()
- else:
- sys.stderr.write("Syntax Error while translating : Expected'('")
- sys.stderr.write("\n")
- exit(2)
- else:
- sys.stderr.write("Syntax Error : unkown notation -->")
- sys.stderr.write(str)
- sys.stderr.write("\n")
- exit(3)
- while len(oplis)>0 :
- if oplis[len(oplis)-1]!='(':
- rpnlis.append(oplis.pop())
- else:
- sys.stderr.write("Syntax Error while translating : Unexpected'('")
- sys.stderr.write("\n")
- exit(1)
- print lis_old
- for i in lis_old:
- sys.stdout.write(i)
- print ''
- print rpnlis
- for i in rpnlis:
- print i,
- print ''
- exit(0)
实验结果:
目前程序的局限:
未进行语法检测
不支持函数变量标识
附录:
算法示意图, 使用了 3 个空间输入用符号代替, 如果输入是一个数字则直接进输出队列, 即图中 b),d),f),h)如果输入是运算符, 则压入操作符堆栈, 即图中 c),e), 但是, 如果输入运算符的优先级低于或等于运算符栈顶的操作符优先级, 则栈内元素进入输出队列(循环判定), 输入操作符压入运算符堆栈, 即图中 g) 最后, 运算符堆栈内元素入输出队列, 算法结束
附录中资料摘自维基百科调度场算法词条
来源: http://www.phperz.com/article/18/0224/361506.html