快捷導(dǎo)航

Python實現(xiàn)調(diào)度算法代碼詳解

更新時間：2017年12月01日 11:50:09 作者：燕云

這篇文章主要介紹了Python實現(xiàn)調(diào)度場算法代碼詳解，具有一定參考價值，需要的朋友可以了解下。

調(diào)度算法

操作系統(tǒng)管理了系統(tǒng)的有限資源，當(dāng)有多個進程（或多個進程發(fā)出的請求）要使用這些資源時，因為資源的有限性，必須按照一定的原則選擇進程（請求）來占用資源。這就是調(diào)度。目的是控制資源使用者的數(shù)量,選取資源使用者許可占用資源或占用資源。

在操作系統(tǒng)中調(diào)度是指一種資源分配，因而調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。對于不同的的系統(tǒng)和系統(tǒng)目標，通常采用不同的調(diào)度算法，例如，在批處理系統(tǒng)中，為了照顧為數(shù)眾多的段作業(yè)，應(yīng)采用短作業(yè)優(yōu)先的調(diào)度算法；又如在分時系統(tǒng)中，為了保證系統(tǒng)具有合理的響應(yīng)時間，應(yīng)當(dāng)采用輪轉(zhuǎn)法進行調(diào)度。目前存在的多種調(diào)度算法中，有的算法適用于作業(yè)調(diào)度，有的算法適用于進程調(diào)度；但也有些調(diào)度算法既可以用于作業(yè)調(diào)度，也可以用于進程調(diào)度。

目標闡述：

將中綴表達式轉(zhuǎn)換為后綴表達式（Reverse Polish Notation：RPN 逆波蘭式）
參與運算的數(shù)據(jù)的正則表示為：[0-9]{1,}形式的十進制數(shù)

運算符優(yōu)先級：（從高到低）————————————————————————
( )   括號
/ * %  除乘余
+ -   加減————————————————————————

解：

第一步：使用正則詞法分析器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進行轉(zhuǎn)換。

從stdin接收一定格式的中綴表達式字符流，檢測是否在詞法分析器處理過程中出錯，然后使用調(diào)度場算法處理數(shù)據(jù)，得到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)

實驗結(jié)果：

目前程序的局限：
未進行語法檢測。
不支持函數(shù)、變量標識。

附錄：

算法示意圖，使用了3個空間。輸入用符號代替，如果輸入是一個數(shù)字則直接進輸出隊列，即圖中 b),d),f),h)。如果輸入是運算符，則壓入操作符堆棧，即圖中 c),e)，但是，如果輸入運算符的優(yōu)先級低于或等于運算符棧頂?shù)牟僮鞣麅?yōu)先級，則棧內(nèi)元素進入輸出隊列（循環(huán)判定），輸入操作符壓入運算符堆棧，即圖中 g)。最后，運算符堆棧內(nèi)元素入輸出隊列，算法結(jié)束。