Обработка польской записи в C#

Цель занятия

Закрепить на практике знания по работе со строками. Изучить возможности представления командных строк в польской записи. Освоить принципы работы со стеком. Дополнительные сведения можно найти в [6, 12].

Краткие теоретические сведения

Польская запись — это запись арифметических выражений, в которой знак операции записывается после аргументов, например:

а b + // Это, конечно, a+b а с + b * // Это (a+c)*b

Достоинство польской записи в том, что она не использует скобки. Наша задача будет состоять в том, чтобы программно вычислить значение простого арифметического выражения, представленного в польской записи, которое использует только целые числа и знаки операций +, — и * (умножить). Следовательно, мы должны научиться вычислять, к примеру, выражения типа такого: 9 45 7 + *.

Несколько упростим себе задачу, используя в качестве разделителей между термами выражения не пробел, а запятую. Таким образом, предыдущая запись превратится в такую: 9,45,7,+,*. Эта запись соответствует обычному представлению вида: 9 * (45 + 7) (ответ: 468).

На форме разместим одно текстовое поле для ввода польской записи, другое текстовое поле — для вывода ответа и кнопку для выполнения расчета. Именно на кнопку и "ложится" вся логика нашего приложения. Наличие разделителя "," позволяет использовать очень "сильную" команду split , которая формирует массив лексем (читай — термов), из которых состоит строка. Наша экранная формадолжна иметь следующий вид (рис. 4.11).

Рис. 4.11. Окно приложения для работы с польской записью

Кнопка PARSE осуществляет вычисление польской записи. Кнопка Clear очищает текстовые поля и список. В списке хранятся все разобранные лексемы входного выражения. Лексемы — это "строительные" элементы выражения: переменные и знаки операций в нашем случае.

Разбор польской записи выполняется с помощью стека — особого вида памяти, для которой возможны следующие операции:

□               записать в стек;

□               прочитать (вытолкнуть) из стека;

□               очистить стек.

В стеке доступен только верхний элемент (иначе — верхушка стека). При записи очередного элемента остальные проталкиваются вглубь стека на одну ячейку, а новый записывается в верхушку. При чтении (выталкивании), напротив, каждый элемент поднимается на одну ячейку вверх.

Алгоритм разбора выполняется таким образом:

(i)Прочитать очередную лексему из входной строки.

(ii)          Если эта лексема не является операцией, то записать ее в стек, иначе — переходим к (iii).

(iii)        Вытолкнуть из стека столько элементов, сколько должно участвовать в данной операции (у нас выталкивается два элемента). Выполнить над ними операцию, а результат загрузить обратно в стек.

(iv)        Перейти к шагу (i), если в строке есть еще лексемы, иначе — конец.

Сначала приведем всю программу (листинг4.17), реализующую этот алгоритм, затем разберем ее подробно.

Листинг 4.17. Приложение для обработки польской записи

using System; using System.Drawing; using System.Collections; using System.ComponentModel; using System.Windows.Forms; using System.Data;

namespace polish

/// <summary>

/// Summary description for Forml.

/// </summa ry>

public class Forml : System.Windows.Forms.Form

public string initstr; public string[] masstr;

private System.Windows.Forms.TextBox textBoxl;

private System.Windows.Forms.Button buttonl; private System.Windows.Forms.TextBox textBox2; private System.Windows.Forms.Label labell; private System.Windows.Forms.ComboBox comboBoxl; private System.Windows.Forms.Button button2;

/// <summary>

/// Required designer variable.

/// </summary>

private System.ComponentModel.Container components = null; public Forml()

{

// Required for Windows Form Designer support //

InitializeComponent();

//

// TODO: Add any constructor code after InitializeComponent // call //

}

/// <summary>

/// Clean up any resources being used.

/// </summary>

protected override void Dispose( bool disposing )

{

if( disposing )

{

if (components != null)

{

components.Dispose ();

}

}

base.Dispose( disposing );

#region Windows Form Designer generated code /// <summary>

/// Required method for Designer support – do not modify /// the contents of this method with the code editor.

/// </summary>

private void InitializeComponent() // Инициализация формы — // это совокупность действий, выполненных системой, поэтому // здесь на ней не следует останавливаться {

this.textBoxl = new System.Windows.Forms.TextBox(); this.buttonl = new System.Windows.Forms.Button(); this.textBox2 = new System.Windows.Forms.TextBox(); this.labell = new System.Windows.Forms.Label(); this.comboBoxl = new System.Windows.Forms.ComboBox(); this.button2 = new System.Windows.Forms.Button(); this.SuspendLayout();

//

// textBoxl //

this.textBoxl.Location = new System.Drawing.Point(72, 72); this.textBoxl.Name = "textBoxl";

this.textBoxl.Size = new System.Drawing.Size(152, 20); this.textBoxl.TabIndex = 0; this.textBoxl.Text = "";

//

// buttonl //

this.buttonl.BackColor =

System.Drawing.Color.FromArgb(((System.Byte)(255)),

((System.Byte) (255)),   ((System.Byte) (128)));

this.buttonl.Location = new System.Drawing.Point(72, 176); this.buttonl.Name = "buttonl";

this.buttonl.Size = new System.Drawing.Size(112, 24); this.buttonl.TabIndex = 1;

this.buttonl.Text = "PARSE";

this.buttonl.Click += new System.EventHandler(this.buttonl_Click);

//

// textBox2 //

this.textBox2.BackColor =

System.Drawing.Color.FromArgb(((System.Byte) (255) ) ,

((System.Byte) (255)),   ((System.Byte) (192)));

this.textBox2.Location = new System.Drawing.Point(184, 112) ;

this.textBox2.Name = "textBox2";

this.textBox2.Size = new System.Drawing.Size(4 0, 20); this.textBox2.TabIndex = 2; this.textBox2.Text = "";

//

// labell //

this.labell.BackColor =

System.Drawing.Color.FromArgb(((System.Byte)(255)),

((System.Byte) (255)),   ((System.Byte) (192)));

this.labell.Location = new System.Drawing.Point(72, 112); this.labell.Name = "labell";

this.labell.Size = new System.Drawing.Size(96, 24); this.labell.TabIndex = 3; this.labell.Text = "result";

//

// comboBoxl //

this.comboBoxl.Location = new System.Drawing.Point(208, 176) ;

this.comboBoxl.Name = "comboBoxl";

this.comboBoxl.Size = new System.Drawing.Size(72, 21);

this.comboBoxl.TabIndex = 4;

this.comboBoxl.Text = "comboBoxl";

//

// button2 //

this.button2.BackColor =

System.Drawing.Color.FromArgb(((System.Byte) (255)) ,

((System.Byte) (255)),   ((System.Byte) (128)));

this.button2.Location = new System.Drawing.Point(72, 216); this.button2.Name = "button2";

this.button2.Size = new System.Drawing.Size(120, 24);

this.button2.TabIndex = 5;

this.button2.Text = "Clear";

this.button2.Click += new System.EventHandler(this.button2_Click);

//

// Forml //

this.AutoScaleBaseSize = new System.Drawing.Size(5, 13); this.BackColor =

System.Drawing.Color.FromArgb(((System.Byte) (255)),

((System.Byte) (192)),   ((System.Byte) (192)));

this.ClientSize = new System.Drawing.Size(292, 273);

this.Controls.Add(this.button2);

this.Controls.Add(this.comboBoxl);

this.Controls.Add(this.labell);

this.Controls.Add(this.textBox2);

this.Controls.Add(this.buttonl);

this.Controls.Add(this.textBoxl);

this.Name = "Forml";

this.Text = "Forml";

this.ResumeLayout(false) ;

}

#endregion /// <summary>

/// The main entry point for the application.

/// </summary>

[STAThread] static void Main()

{

Application.Run(new Forml());

}

private void buttonl_Click(object sender,

System.EventArgs e)

{

initstr=textBoxl.Text; // Это — разбираемое выражение masstr=initstr.Split(‘,’); // masstr — массив, в который

// записываются лексемы for(int j=0;j<masstr.Length;j++)

{ comboBoxl.Items.Add(masstr[j]); } // В комбо-список

// заносим // все распознанные // лексемы string[]stack=new string[masstr.Length];

decimal res=0; // В переменной res получаем окончательный // результат

for( int i=0;i<masstr.Length;i++) // В этом цикле // выполняется разбор и обработка польской записи,

// лексемы которой сохранены в массиве строк masstr {

if ((masstr[i]="+")|(masstr[i]="-")|   (masstr[i]=="*")|

(masstr[i]="/") )

{

string sl=stack[l]; string s0=stack[0]; for (int iw=2;iw<stack.Length;iw++)

{ stack[iw-l]=stack[iw]; } decimal il=Convert.ToDecimal(sl); decimal i2=Convert.ToDecimal(s0); switch (masstr[i])

case "+": res=il+i2; stack[0]=""+res; break; case "-": res=il-i2; stack[0]=""+res; break; case "*": res=il*i2; stack[0]=""+res; break; case "/": res=il/i2; stack[0]=""+res; break;

}

}

else

{

if(stack.Length==O) {stack[0]=masstr[i];} else {

for (int j =0;j<stack.Length-1;j ++)

stack[j+l]=stack[j]; stack[0]=masstr[i] ;

}

}

}

textBox2.Text=""+res;

private void button2_Click(object sender,

System.EventArgs e)

{

initstr=""; textBoxl.Text=""; textBox2.Text=""; comboBoxl.Items.Clear() ;

}

}

}

Самая простая — это кнопка Clear:

private void button2_Click(object sender, System.EventArgs e)

{

initstr=""; textBoxl.Text=""; textBox2.Text=""; comboBoxl.Items.Clear() ;

}

Пояснять ее, вероятно, не следует. Обратимся к кнопке PARSE. Сначала мы формируем массив лексем:

initstr=textBoxl.Text; // Это — разбираемое выражение masstr=initstr.Split(‘,’) ;

Отметим, что в качестве разделителя используется запятая.

Разбор лексем выполняется так. Если встречается число, то оно грузится в стек — массив stack. Если встречается знак операции, то выполняются следующие команды:

if ((masstr[i]="+")|(masstr[i]="-")| (masstr[i]="*") |

(masstr[i]="/")) // "|" — Знак "ИЛИ"; выполняется проверка // того, что лексема суть операция { // Встретился знак операции string sl=stack[l];

string s0=stack[0]; // Выгружаем из стека верхние два // операнда

for (int iw=2;iw<stack.Length;iw++) // Передвигаем остальные // операнды в стеке наверх на одну ячейку {

stack[iw-l]=stack[iw];

}

decimal il=Convert.ToDecimal(sl); // Преобразуем прочитанные // два операнда из стека в вещественные числа — тип decimal decimal i2=Convert.ToDecimal(s0) ; switch (masstr[i])

{ // Анализируем знак операции case "+":

res=il+i2; // Если +, то складываем stack[0]=""+res; break; case "-":

res=il-i2; // Если -, то вычитаем stack[0]=""+res; break; case "*":

res=il*i2; // Умножение для знака * stack[0]=""+res; break; case "/":

res=il/i2; // Деление для знака /

stack[0]=""+res;

break;

}

}

Если лексема не оператор, то ее загружаем в стек:

else

if (stack.Length==O)

{stack[0]=masstr[i];} else {

for (int j = 0;j<stack.Length-1;j ++)

stack[j+1]=stack[j]; stack[0]=masstr[i];

}

}

}

Если стек не пуст, то загрузку выполняем так:

for (int j =0;j<stack.Length-1;j ++) stack[j+l]=stack[j];

/ / Элементы проталкиваем на следующую ячейку стека stack[0]=masstr[i]; // Считанная лексема грузится в верхушку // стека

Итак, основная процедура обработки польского выражения нами последовательно разобрана.

Задание

Выполните алгоритм разбора польской записи сначала вручную и убедитесь в том, что вы его хорошо понимаете. Затем разберитесь в программе.

Требуется расширить функциональные возможности программы следующим образом:

□               разделителем лексем должен быть символ пробела;

□               программа должна обнаруживать неправильные синтаксические конструкции типа 2 + 3 *;

□               числа должны быть вещественными с фиксированной точкой: например: 20.6;

□               предусмотреть возможность работы с отрицательными числами;

□               предусмотреть возможность использования операторов присваивания. В этом случае вам понадобится хранить значения

переменных, например, используя для этих целей еще один массив с двумя столбцами: в первом столбце записываем имена переменных, во втором — их значения.

Источник: Герман О. B., Герман Ю. О., Программирование на Java и C# для студента. — СПб.: БХВ-Петербург, 2005. — 512 c.: ил.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100