如何将前缀表达式正确读入并且按中缀表达式输出？(100分)

如读入：-ab 输出a-b;(a,b均为变量）
读入：*+abc/d 输出：(a+b)*c/d
请用2叉树实现。能给出源代码吗？
多谢。

pascal的,几乎不做修改就可以用在Delphi上.
等一下.

找不到了 :-(
不过,有一个练习使用二叉树的例子:

unit SortNode;

interface

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

type
TSortNode = class(TObject)
public
node_value : Integer;
left_child, right_child : TSortNode;
position : TRect;

constructor Create;
destructor Destroy
override;
procedure SetPosition(var start_x : Integer
start_y : Integer);
procedure DrawNode(cvs : TCanvas);
procedure DrawSubtree(cvs : TCanvas);
procedure AddNode(new_value : Integer);
function Preorder : String;
function Inorder : String;
function Postorder : String;
function BreadthFirst : String;
end;

TSortTreeForm = class(TForm)
Label1: TLabel;
txtValue: TEdit;
cmdAdd: TButton;
grpTraversal: TRadioGroup;
lblTraversal: TLabel;
procedure FormCreate(Sender: TObject);
procedure FormPaint(Sender: TObject);
procedure txtValueChange(Sender: TObject);
procedure cmdAddClick(Sender: TObject);
procedure grpTraversalClick(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;

var
SortTreeForm: TSortTreeForm;

implementation

{$R *.DFM}

const
BOX_WID = 40;
BOX_HGT = 16;
BOX_HGAP = 2;
BOX_VGAP = 6;
var
root : TSortNode;
tree_xmin, tree_ymin : Integer;

// **************************
// * TBigTreeForm functions *
// **************************
// Calculate the tree position.
procedure TSortTreeForm.FormCreate(Sender: TObject);
begin
// Save the coordinates where we will start drawing.
tree_xmin := grpTraversal.Left + grpTraversal.Width + 3;
tree_ymin := cmdAdd.Top + cmdAdd.Height + 3;
end;

// Draw the tree.
procedure TSortTreeForm.FormPaint(Sender: TObject);
var
rect : TRect;
begin
// Erase the canvas.
rect.Left := 0;
rect.Right := Width;
rect.Top := 0;
rect.Bottom := Height;
Canvas.Brush.Color := clLtGray;
Canvas.FillRect(rect);

// Draw the tree.
if (root <> nil) then root.DrawSubtree(Canvas);
end;

// Enable and disable buttons appropriately.
procedure TSortTreeForm.txtValueChange(Sender: TObject);
begin
cmdAdd.Enabled := (Trim(txtValue.Text) <> '');
end;

// Add a new node in its sorted position.
procedure TSortTreeForm.cmdAddClick(Sender: TObject);
var
new_value, start_x : Integer;
begin
new_value := StrToInt(txtValue.Text);

if (root = nil) then
begin
// Create a new root node.
root := TSortNode.Create;
root.node_value := new_value;
end else begin
// Add the child to the root's subtree.
root.AddNode(new_value);
end;

// Reposition the nodes.
start_x := tree_xmin;
root.SetPosition(start_x, tree_ymin);

// Redraw the tree.
Refresh;

// Erase the value TextBox and give it focus.
txtValue.Text := '';
txtValue.SetFocus;
end;

// Display the selected traversal.
procedure TSortTreeForm.grpTraversalClick(Sender: TObject);
begin
if (root <> nil) then
begin
case grpTraversal.ItemIndex of
0: lblTraversal.Caption := root.Preorder;
1: lblTraversal.Caption := root.Inorder;
2: lblTraversal.Caption := root.Postorder;
3: lblTraversal.Caption := root.BreadthFirst;
end;
end;
end;

// **********************
// * TSortNode functions *
// **********************
// Create the children list.
constructor TSortNode.Create;
begin
inherited Create;
left_child := nil;
right_child := nil;
end;

// Free any children.
destructor TSortNode.Destroy;
begin
// Free the children.
left_child.Free;
right_child.Free;

inherited Destroy;
end;

// Position the node and its descendants. Update start_x
// so it indicates the rightmost position used by the
// node and its descendants.
procedure TSortNode.SetPosition(var start_x : Integer
start_y : Integer);
var
xmin : Integer;
begin
// Set the node's top and bottom.
position.Top := start_y;
position.Bottom := start_y + BOX_HGT;

// Record the leftmost position used.
xmin := start_x;

// If there are no children, put the node here.
if ((left_child = nil) and (right_child = nil)) then
begin
start_x := xmin + BOX_WID;
end else begin
// This is where the children will start.
start_y := start_y + BOX_HGT + BOX_VGAP;

// Position the left subtree.
if (left_child <> nil) then
begin
// Position this child.
left_child.SetPosition(start_x, start_y);

// Add a little room before the next child.
start_x := start_x + BOX_HGAP;
end;

// Position the right subtree.
if (right_child <> nil) then
begin
// Position this child.
right_child.SetPosition(start_x, start_y);

// Add a little room before the next child.
start_x := start_x + BOX_HGAP;
end;

// Subtract the gap after the last child.
start_x := start_x - BOX_HGAP;
end;

// Center this node over its children.
position.Left := (xmin + start_x - BOX_WID) div 2;
position.Right := position.Left + BOX_WID;
end;

// Draw this node.
procedure TSortNode.DrawNode(cvs : TCanvas);
var
text_size : TSize;
txt : String;
begin
// Erase the node's position and draw a box.
cvs.FillRect(position);
cvs.Rectangle(
position.Left, position.Top,
position.Right, position.Bottom);

// Draw the node's value text.
txt := IntToStr(node_value);
text_size := cvs.TextExtent(txt);
cvs.TextOut(
(position.Left + position.Right - text_size.cx) div 2,
(position.Top + position.Bottom - text_size.cy) div 2,
txt);
end;

// Draw the subtree rooted at this node.
procedure TSortNode.DrawSubtree(cvs : TCanvas);
begin
// Draw this node.
DrawNode(cvs);

// Draw the left subtree.
if (left_child <> nil) then
begin
// Draw the subtree itself.
left_child.DrawSubtree(cvs);

// Draw lines connecting the node and the child.
cvs.MoveTo(
position.Left + BOX_WID div 2,
position.Top + BOX_HGT);
cvs.LineTo(
left_child.position.Left + BOX_WID div 2,
left_child.position.Top);
end;

// Draw the right subtree.
if (right_child <> nil) then
begin
// Draw the subtree itself.
right_child.DrawSubtree(cvs);

// Draw lines connecting the node and the child.
cvs.MoveTo(
position.Left + BOX_WID div 2,
position.Top + BOX_HGT);
cvs.LineTo(
right_child.position.Left + BOX_WID div 2,
right_child.position.Top);
end;
end;

// Add a new node to this subtree.
procedure TSortNode.AddNode(new_value : Integer);
begin
// See which child to examine.
if (new_value < node_value) then
begin
// Add it to the left subtree.
if (left_child = nil) then
begin
// Create the new child here.
left_child := TSortNode.Create;
left_child.node_value := new_value;
end else begin
// Add it to the subtree.
left_child.AddNode(new_value);
end;
end else begin
// Add it to the right subtree.
if (right_child = nil) then
begin
// Create the new child here.
right_child := TSortNode.Create;
right_child.node_value := new_value;
end else begin
// Add it to the subtree.
right_child.AddNode(new_value);
end;
end;
end;

// Return the subtree's preorder traversal.
function TSortNode.Preorder : String;
begin
Result := IntToStr(node_value);
if (left_child <> nil) then
Result := Result + ' ' + left_child.Preorder;
if (right_child <> nil) then
Result := Result + ' ' + right_child.Preorder;
end;

// Return the subtree's inorder traversal.
function TSortNode.Inorder : String;
begin
Result := '';
if (left_child <> nil) then
Result := Result + left_child.Inorder + ' ';
Result := Result + IntToStr(node_value);
if (right_child <> nil) then
Result := Result + ' ' + right_child.Inorder;
end;

// Return the subtree's postorder traversal.
function TSortNode.Postorder : String;
begin
Result := '';
if (left_child <> nil) then
Result := Result + left_child.Postorder + ' ';
if (right_child <> nil) then
Result := Result + right_child.Postorder + ' ';
Result := Result + IntToStr(node_value);
end;

// Return the subtree's breadth-first traversal.
function TSortNode.BreadthFirst : String;
var
nodes : TList;
node : TSortNode;
begin
Result := '';

// Create the node list.
nodes := TList.Create;

// Put the root node on the list of nodes.
nodes.Add(root);

// While the list of nodes is not empty...
while (nodes.Count > 0) do
begin
// Output the first item and remove it
// from the list.
node := nodes.Items[0];
nodes.Delete(0);
Result := Result + IntToStr(node.node_value) + ' ';

// Add the node's children to the stack.
if (node.left_child <> nil) then
nodes.Add(node.left_child);
if (node.right_child <> nil) then
nodes.Add(node.right_child);
end;

// Destroy the list of nodes.
nodes.Free;
end;

end.

找本数据结构，照搬即可。

只谈思想：先将所要读入的前缀表达式作成一棵二叉树，然后按中序遍历此二叉树即可。具体算法参见《数据结构》，上面写的很清楚。

这样的小东东，用栈模仿就可以了。

多谢beta及各位。
忘了说一句，a,b等均为变量，可以每次对其赋不同的值，然后得出表达式的值。
如何做？

SuperMMX:
怎样模仿？能给出源代码吗？

现在不行，没法做，求值用后缀较简单，
我原来贴过的，
http://www.gislab.ecnu.edu.cn/delphibbs/DispQ.asp?LID=231166

是中缀化后缀，并计算，直接输入数字。

另：呵呵，我都赚了两三个人的分了，

模仿堆栈比较容易,通常用数组模拟:
const max=1000;//堆栈最大深度
var
s:array[1..max] of integer;
i,p:integer;
...
procedure pushstack(data:integer);//模拟push
begin
if p=max then exit;//堆栈溢出
inc(p);
s[p]:=data;
end;

procedure popstack(var data:integer);//模拟pop
begin
if p=0 then exit;//堆栈空
data:=s[p];
dec(p);
end;
...
begin
p:=0;//栈顶指针
for i := 1 to 100 do pushstack(i);
...
end.

呵呵， beta 可不是这个模拟法，

还是自己慢慢搞定了。多谢各位。