Python实现调度场算法详解：从中缀表达式到后缀表达式

唐可

发布时间：2026-10-13| 2人浏览过

原创

本文详细讲解如何使用Python实现调度场算法，将中缀表达式转换为后缀表达式（RPN）。通过结合lex词法分析器与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)。最后，运算符堆栈内元素入输出队列，算法结束。