unit1.pas

实现数据结构中的数学中序表达式转换为后继表达式. 并且运算出后序表达式的结果. 运算符号包括 + - * / & | ! ( ) 加 减 乘 除 与 或 非

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, Math;

type
  TOperator = ( oPlus=0, oMinus=1, oMutil=2, oDiv=3, oAnd=4, oOr=5, oNot=6,
                oLBra=7, oRBra=8, oEnd=9 );
  TPriorityArr = array [TOperator] of Integer;

const
  sOperatorSet: set of Char = [ '+', '-', '*', '/', '&', '|', '!', '(', ')', '#' ];

  sOperatorTocken: array [TOperator] of Char =
    ('+', '-', '*', '/', '&', '|', '!', '(', ')', '#');

  iOperatorPriority: array [TOperator] of TPriorityArr =
   (// +,  -,  *,  /,  &,  |,  !   (,  ),  #
     ( 1,  1, -1, -1, -1, -1, -1, -1,  1,  1), // +
     ( 1,  1, -1, -1, -1, -1, -1, -1,  1,  1), // -
     ( 1,  1,  1,  1,  1,  1,  1, -1,  1,  1), // *
     ( 1,  1,  1,  1,  1,  1,  1, -1,  1,  1), // /
     ( 1,  1,  1,  1,  1,  1,  1, -1,  1,  1), // &
     ( 1,  1,  1,  1,  1,  1,  1, -1,  1,  1), // |
     ( 1,  1,  1,  1,  1,  1,  1, -1,  1,  1), // !
     (-1, -1, -1, -1, -1, -1, -1, -1,  0, -2), // (
     ( 1,  1,  1,  1,  1,  1,  1, -2,  1,  1), // )
     (-1, -1, -1, -1, -1, -1, -1, -1, -2,  0)  // #
   );

type
  TLinkStack = record
    pchData: array of Char;                                                     // 数据
    pNext: Pointer;                                                             // 链
  end;

  TStack = class
  private
    m_pTop: ^TLinkStack;                                                        // 头
  public
    procedure Clear;                                                            // 清空
    function Pop( var sData: String ): Boolean;                                 // 弹出
    procedure Push( const sData: String );                                      // 压栈

    constructor Create; virtual;
    destructor Destroy; override;
  end;

  TForm1 = class(TForm)
    Button1: TButton;
    Edit1: TEdit;
    btn1: TButton;
    mmo1: TMemo;
    Button2: TButton;
    Edit2: TEdit;
    Button3: TButton;
    procedure FormCreate(Sender: TObject);
    procedure FormDestroy(Sender: TObject);
    procedure Button1Click(Sender: TObject);
    procedure btn1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
    procedure Button3Click(Sender: TObject);
  private
    { Private declarations }
    m_pStack: TStack;
  public
    function ChangeFormat( sOrgin: String; var sRes: String ): Boolean;
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

{ TStack }

procedure TStack.Clear;
var
  pTmp: ^TLinkStack;
begin
  pTmp := Pointer(m_pTop);
  while pTmp <> nil do
  begin
    pTmp := m_pTop^.pNext;
    Setlength( m_pTop^.pchData, 0 );
    Dispose( m_pTop );
    m_pTop := Pointer(pTmp);
  end;
  m_pTop := nil;
end;

constructor TStack.Create;
begin
  m_pTop := nil;
end;

destructor TStack.Destroy;
begin
  Clear;
  inherited;
end;

function TStack.Pop(var sData: String): Boolean;
var
  pTmp: ^TLinkStack;
begin
  Result := False;
  if m_pTop = nil then Exit;
  Result := True;
  pTmp := m_pTop^.pNext;
  sData := '';
  sData := Trim(String(m_pTop^.pchData));
  SetLength( m_pTop^.pchData, 0 );
  Dispose( m_pTop );
  m_pTop := Pointer(pTmp);
  if pTmp <> nil then
    m_pTop := Pointer(pTmp)
  else begin
    m_pTop := nil;
  end;
end;

procedure TStack.Push(const sData: String);
var
  pTmp: ^TLinkStack;
  nLen: Integer;
begin
  New(pTmp);
  nLen := Length(sData) + 1;

  SetLength( pTmp^.pchData, nLen );
  StrCopy( @(pTmp^.pchData[0]), PChar(sData) );
  pTmp^.pchData[nLen] := #0;
  pTmp^.pNext := m_pTop;
  m_pTop := Pointer(pTmp);
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
  m_pStack := TStack.Create;
end;

procedure TForm1.FormDestroy(Sender: TObject);
begin
  m_pStack.Free;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
  m_pStack.Push( Edit1.Text );
end;

procedure TForm1.btn1Click(Sender: TObject);
var
  s: string;
begin
  if m_pStack.Pop( s ) then mmo1.Lines.Add( s );
end;

function TForm1.ChangeFormat( sOrgin: String;
  var sRes: String): Boolean;
  function TranslateOrd( s: string ): TOperator;
  begin
    s := Trim(s);
    if      s = sOperatorTocken[oPlus]  then Result := oPlus
    else if s = sOperatorTocken[oMinus] then Result := oMinus
    else if s = sOperatorTocken[oMutil] then Result := oMutil
    else if s = sOperatorTocken[oDiv]   then Result := oDiv
    else if s = sOperatorTocken[oAnd]   then Result := oAnd
    else if s = sOperatorTocken[oOr]    then Result := oOr
    else if s = sOperatorTocken[oNot]   then Result := oNot
    else if s = sOperatorTocken[oLBra]  then Result := oLBra
    else if s = sOperatorTocken[oRBra]  then Result := oRBra
    else if s = sOperatorTocken[oEnd]   then Result := oEnd
  end;
var
  i: Integer;
  Q1, Q2: TOperator;
  s: String;
begin
  sOrgin := sOrgin + '#';
  sOrgin := StringReplace(sOrgin, ' ', '', [rfReplaceAll]);
  sOrgin := StringReplace(sOrgin, #$D#$A, '', [rfReplaceAll]);
  Length(sOrgin);
  i := 1;
  sRes := '';
  m_pStack.Push('#');
  mmo1.Lines.Clear;
  while sOrgin[i] <> #0 do
  begin
    if sOrgin[i] in sOperatorSet then
    begin
      if sOrgin[i] = sOperatorTocken[oMinus] then
      begin
        if (i = 1) or
           ( sOrgin[i-1] in ['(', '*', '/', '+', '&', '|', '!'] ) then
        begin
          sRes := sRes + sOrgin[i];
          Inc(i);
          Continue;
        end;
      end;
      if sRes <> '' then
        mmo1.Lines.Add( sRes );
      sRes := '';
      m_pStack.Pop(s);
      Q1 := TranslateOrd(s);
      Q2 := TranslateOrd(sOrgin[i]);
      case iOperatorPriority[Q1][Q2] of
         1: begin
              mmo1.Lines.Add(s);
              while m_pStack.Pop(s) do
              begin

                Q1 := TranslateOrd(s);
                Q2 := TranslateOrd(sOrgin[i]);
                case iOperatorPriority[Q1][Q2] of
                  1: begin
                       mmo1.Lines.Add(s);
                       //sRes := sRes + s;
                     end;
                 -1: begin
                       m_pStack.Push(s);
                       m_pStack.Push(sOrgin[i]);
                       Break;
                     end;
                  0: begin
                       if (s = sOperatorTocken[oLBra]) and
                          (sOrgin[i] = sOperatorTocken[oRBra]) then
                         Break
                       else if (s = sOperatorTocken[oEnd]) and
                               (sOrgin[i] = sOperatorTocken[oEnd]) then
                         Exit;
                     end;
                 -2: begin
                       raise Exception.Create('表达式错误!');
                     end;
                 end;
              end;

            end;
        -1: begin
              m_pStack.Push(s);
              m_pStack.Push(sOrgin[i]);
            end;
         0: begin
              if (s = sOperatorTocken[oLBra]) and
                 (sOrgin[i] = sOperatorTocken[oRBra]) then
              begin
                Inc(i);
                Continue;
              end;
            end;
        -2: begin
              raise Exception.Create('表达式错误!');
            end;
      end;
    end
    else
      sRes := sRes + sOrgin[i];
    Inc(i);
  end;
end;

procedure TForm1.Button2Click(Sender: TObject);
var
  s: String;
begin
  ChangeFormat( Edit2.Text, s );
end;



procedure TForm1.Button3Click(Sender: TObject);
var
  i: Integer;
  t, t1, t2: Double;
begin
  i := 0;
  while mmo1.Lines.Count > 1 do
  begin
    if (Length(mmo1.Lines[i]) = 1) and (mmo1.Lines[i][1] in sOperatorSet) then
    begin
      case i of
       1: begin                                                                 // 符号
            TryStrToFloat( mmo1.Lines[i-1], t1 );
            if mmo1.Lines[i] = sOperatorTocken[oMinus] then
              t1 := -t1
            else if  mmo1.Lines[i][1] = sOperatorTocken[oNot] then
              t1 := not Floor(t1);
            mmo1.Lines[i-1] := FloatToStr(t1);
            mmo1.Lines.Delete( i );
            Continue;
          end;
      else
        if not TryStrToFloat( mmo1.Lines[i-1], t1 ) then
          raise Exception.Create('算式有误!');

        if mmo1.Lines[i][1] = sOperatorTocken[oNot] then
        begin
          t1 := not Floor(t1);
          mmo1.Lines[i-1] := FloatToStr(t1);
          mmo1.Lines.Delete( i );
          Continue;
        end;

        if not TryStrToFloat( mmo1.Lines[i-2], t2 ) then
        begin
          if mmo1.Lines[i] = sOperatorTocken[oMinus] then
            t1 := -t1;
          mmo1.Lines[i-1] := FloatToStr(t1);
          mmo1.Lines.Delete( i );
        end
        else begin
          case mmo1.Lines[i][1] of
            '+': t := t2 + t1;
            '-': t := t2 - t1;
            '*': t := t2 * t1;
            '/': t := t2 / t1;
            '&': t := Floor(t2) and Floor(t1);
            '|': t := Floor(t2) or Floor(t1);
          end;
          mmo1.Lines[i-2] := FloatToStr(t);
          mmo1.Lines.Delete( i );
          mmo1.Lines.Delete( i - 1 );
          Dec(i);
          Continue;
        end;
      end;
    end;
    Inc(i);
  end;
end;

end.