VPF::[C++] Разложение арифметических действий в дерево

OLESYAaa

Дата 30.5.2009, 16:29 (ссылка)

(голосов:3)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 4
Регистрация: 29.5.2009

Репутация: нет
Всего: нет

помогите пожалуйста !мне надо на си++ написать программу, кторая при вводе какогото арифмитического действия выдает как бы дерево разложения. например (х+5)*(3-(а-8)) и надо чтоб получилось * дальше 2 стрелочки в одной плюс (и из нее отходит опять 2 стрелочки в одной 5 в другой х, вот ) а в другой минус потом из нее 2 стрелочки в одной а в другой минус от нее еще 2 стрелочки в одной а в другой 8, ну короче разложение такое!!
вот это то или нет,я не пойму(

Код


#include<stdio.h>
#include<stdlib.h>

 /* Описание стpуктуpы(элемента стека) */
struct st                
{ char c;struct st *next;};
struct st *push(struct st *, char); 
/* Пpототипы функций */
char DEL(struct st **);
int PRIOR(char);

void main(void)
{
  /* Стек опеpаций пуст */
  struct st *OPERS=NULL;                     
  char a[80], outstring[80];
  int k, point;
  do
  { puts("Введите выpажение(в конце '='):");
    fflush(stdin);
    /* Ввод аpифметического выpажения */
    gets(a);                                 
    k=point=0;
      /* Повтоpяем , пока не дойдем до '=' */
    while(a[k]!='\0'&&a[k]!='=')           
    {
    /* Если очеpедной символ - ')' */
      if(a[k]==')')             
                 /* то выталкиваем из стека в выходную стpоку */
      {                                     
              /* все знаки опеpаций до ближайшей */
        while((OPERS->c)!='(')         
              /* откpывающей скобки */
        outstring[point++]=DEL(&OPERS);  
              /* Удаляем из стека саму откpывающую скобку */
        DEL(&OPERS);
      }
                    /* Если очеpедной символ - буква , то */
      if(a[k]>='a'&&a[k]<='z')        
              /* пеpеписываем её в выходную стpоку */
          outstring[point++]=a[k];        
                    /* Если очеpедной символ - '(' , то */
      if(a[k]=='(')                         
              /* заталкиваем её в стек */
          OPERS=push(OPERS, '(');           
      if(a[k]=='+'||a[k]=='-'||a[k]=='/'||a[k]=='*')
      /* Если следующий символ - знак опеpации , то: */
      {                             
                /* если стек пуст */
        if(OPERS==NULL)                     
         /* записываем в него опеpацию */
            OPERS=push(OPERS, a[k]);        
             /* если не пуст */
        else                                 
/* если пpиоpитет поступившей опеpации больше 
               пpиоpитета опеpации на веpшине стека */
        if(PRIOR(OPERS->c)<PRIOR(a[k]))      
        /* заталкиваем поступившую опеpацию на стек */             
            OPERS=push(OPERS, a[k]);      
                   /* если пpиоpитет меньше */
        else                              
        {
          while((OPERS!=NULL)&&(PRIOR(OPERS->c)>=PRIOR(a[k])))
/* пеpеписываем в выходную стpоку все опеpации
                   с большим или pавным пpиоpитетом */
              outstring[point++]=DEL(&OPERS); 
                /* записываем в стек поступившую  опеpацию */
          OPERS=push(OPERS, a[k]);           
        } 
      }
      /* Пеpеход к следующему символу входной стpоки */
      k++;                                    
    }
       /* после pассмотpения всего выpажения */
    while(OPERS!=NULL)                     
     /* Пеpеписываем все опеpации из */
        outstring[point++]=DEL(&OPERS);    
          /* стека в выходную стpоку */
    outstring[point]='\0';                    
       /* и печатаем её */
    printf("\n%s\n", outstring);            
    fflush(stdin);
    puts("\nПовтоpить(y/n)?");
  } while(getchar()!='n');
}

/* Функция push записывает на стек (на веpшину котоpого указывает HEAD)
   символ a . Возвpащает указатель на новую веpшину стека */
struct st *push(struct st *HEAD, char a)
{
  struct st *PTR;
  /* Выделение памяти */
  if((PTR=malloc(sizeof(struct st)))==NULL) 
  {
  /* Если её нет - выход */
    puts("ет памяти");exit(-1);             
  }
  /* Инициализация созданной веpшины */
  PTR->c=a;                                
   /* и подключение её к стеку */
  PTR->next=HEAD;           
   /* PTR -новая веpшина стека */
  return PTR;                               
}

/* Функция DEL удаляет символ с веpшины стека.
   Возвpащает удаляемый символ.
   Изменяет указатель на веpшину стека */
char DEL(struct st **HEAD)
{
  struct st *PTR;
  char a;
  /* Если стек пуст,  возвpащается '\0' */
  if(*HEAD==NULL) return '\0'; 
  /* в PTR - адpес веpшины стека */
  PTR=*HEAD;                   
  a=PTR->c;
  /* Изменяем адpес веpшины стека */
  *HEAD=PTR->next;         
  /* Освобождение памяти */
  free(PTR);   
   /* Возвpат символа с веpшины стека */                
  return a;                   
}

/* Функция PRIOR возвpащает пpиоpитет аpифм. опеpации */
int PRIOR(char a)
{
  switch(a)
  {
    case '*':
    case '/':
         return 3;

    case '-':
    case '+':
         return 2;

    case '(':
         return 1;
  }
}

M
MAKCim

Модератор: Впредь пользуйтесь тегом код !

andrew_121

Дата 30.5.2009, 17:06 (ссылка)

(нет голосов)

Загрузка ...

Кодофей

Профиль
Группа: Завсегдатай
Сообщений: 3448
Регистрация: 3.1.2008

Репутация: 0
Всего: 33

OLESYAaa, Может Вы расскажете что с вашей программой не так? smile

--------------------

Удалил аккаунт. Прощайте!

Бонифаций

Дата 30.5.2009, 18:05 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 827
Регистрация: 15.9.2005
Где: Brisbane

Репутация: 1
Всего: 40

Цитата(OLESYAaa @ 30.5.2009, 16:29

)

/* Ввод аpифметического выpажения */
gets(a);

Писали явно студенты..

Ваша программа производит синтаксический разбор упрощенного выражения методом стека с приоритетами и выводит результат в виде обратной польской записи. Деревом тут не пахнет.

--------------------

Бонифаций.

OLESYAaa

Дата 30.5.2009, 18:06 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 4
Регистрация: 29.5.2009

Репутация: нет
Всего: нет

мне надо чтоб дерево было а там нету дерева, там просто эти все символы по порядку идут, тоесть как бы для дерева их сортируют, в каком порядке они должны идти, там * например потом+ потом х5 ну короче так. а мне надо чтоб дерево выдаавло

Добавлено через 36 секунд
а как мне дерево сделать?((((

Добавлено через 2 минуты и 35 секунд
вот еще архив такой есть,мне из всего этого надо както программу сложить(

Присоединённый файл ( Кол-во скачиваний: 7 )

expr.zip 4,40 Kb

andrew_121

Дата 30.5.2009, 18:14 (ссылка)

(нет голосов)

Загрузка ...

Кодофей

Профиль
Группа: Завсегдатай
Сообщений: 3448
Регистрация: 3.1.2008

Репутация: 0
Всего: 33

Цитата(OLESYAaa @ 30.5.2009, 18:06

)

мне надо чтоб дерево было а там нету дерева, там просто эти все символы по порядку идут, тоесть как бы для дерева их сортируют, в каком порядке они должны идти, там * например потом+ потом х5 ну короче так. а мне надо чтоб дерево выдаавло

Добавлено через 36 секунд
а как мне дерево сделать?((((

Добавлено через 2 минуты и 35 секунд
вот еще архив такой есть,мне из всего этого надо както программу сложить(

Простите. А Вы случаем не блондинка? smile

И еще раз простите. Вы пары на которых изучали информатику посещали? smile

--------------------

Удалил аккаунт. Прощайте!

Бонифаций

Дата 30.5.2009, 18:18 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 827
Регистрация: 15.9.2005
Где: Brisbane

Репутация: 1
Всего: 40

то что вы приложили это не zip файл.

--------------------

Бонифаций.

andrew_121

Дата 30.5.2009, 18:24 (ссылка)

(нет голосов)

Загрузка ...

Кодофей

Профиль
Группа: Завсегдатай
Сообщений: 3448
Регистрация: 3.1.2008

Репутация: 0
Всего: 33

Бонифаций, Да нет же, зип.

--------------------

Удалил аккаунт. Прощайте!

Бонифаций

Дата 30.5.2009, 18:28 (ссылка)

(голосов:1)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 827
Регистрация: 15.9.2005
Где: Brisbane

Репутация: 1
Всего: 40

если посмотреть потроха, видно что этот rar.
А unzip на него ругается

Код


unzip expr.zip 
Archive:  expr.zip
  End-of-central-directory signature not found.  Either this file is not
  a zipfile, or it constitutes one disk of a multi-part archive.  In the
  latter case the central directory and zipfile comment will be found on
  the last disk(s) of this archive.
unzip:  cannot find zipfile directory in one of expr.zip or
        expr.zip.zip, and cannot find expr.zip.ZIP, period.

--------------------

Бонифаций.

OLESYAaa

Дата 30.5.2009, 18:42 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 4
Регистрация: 29.5.2009

Репутация: нет
Всего: нет

я не блондинка(((блин, ну просто программирование вообще не дается, я както в первом семестре пыталась чето писать. понимать, потом все хуже и хуже((я не знаю вооьще что уже делать((мне до вт надо написать программу((а то меня отчислят((пары я посещала все, но НИКАК не дается. вот честно слово((((помогите пожалуйста, можно чтото сделать из этого архивуа и программы...??

Добавлено @ 18:45

Код

#include <iostream>
#include <math.h>
#include "stack.h"
//------------------------------------------------------------------------------
typedef double(*pfun)(double);
struct Func{
char *name,shortname;
pfun fun; };
//------------------------------------------------------------------------------
double fnull(double x){return x;}
//------------------------------------------------------------------------------
const Func FTable[]={{"arcsin",'á',asin},
{"arccos",'â',acos},
{"arctg",'ã',atan},
{"sin",'ä',sin},
{"cos",'æ',cos},
{"tg",'ç',tan},
{"exp",'è',exp},
{"log",'ë',log},
{"abs",'ì',fabs},
{"",'ÿ',fnull}};
const int SizeFTable=sizeof(FTable)/sizeof(FTable[0]);
//------------------------------------------------------------------------------
class Node{
public:
virtual double calc()=0;
virtual void print()=0;
virtual ~Node(){}; };
//------------------------------------------------------------------------------
class NumNode: public Node{
const double num;
public:
NumNode(double NUM):num(NUM){};
double calc(){return num;}
void print(){std::cout<<num;} };
//------------------------------------------------------------------------------
class ParameterNode: public Node{
const char ch;
public:
ParameterNode(char CH):ch(CH){}
void print(){std::cout<<ch;}
double calc(){
std::cout<<ch<<"=";
double x; std::cin>>x; return x;} };
//------------------------------------------------------------------------------
class UnNode: public Node{
protected:
Node *child;
public:
UnNode(Node *CHILD):child(CHILD){}
~UnNode(){delete child;} };
//------------------------------------------------------------------------------
class UnMinusNode: public UnNode{
public:
UnMinusNode(Node *CHILD):UnNode(CHILD){}
double calc(){return -(child->calc());}
void print(){std::cout<<"-("; child->print(); std::cout<<")";}
};



//------------------------------------------------------------------------------
class UnFuncNode: public UnNode{
unsigned char fnum;
public:
UnFuncNode(char s,Node *CHILD):UnNode(CHILD){
int i=0; for(i=0; i<SizeFTable;++i){
fnum=i;
if(FTable[i].shortname==s){break;}
i=(i>=SizeFTable)?(SizeFTable-1):i;}}
double calc(){return (FTable[fnum].fun)(child->calc());}
void print(){std::cout<<FTable[fnum].name<<"("; child->print();
std::cout<<")";}
};
//------------------------------------------------------------------------------
class UnPlusNode: public UnNode{
public:
UnPlusNode(Node *CHILD):UnNode(CHILD){}
double calc(){return child->calc();}
void print(){child->print();}
};
//------------------------------------------------------------------------------
class BinNode: public Node{
protected:
Node *left,*right;
public:
BinNode(Node *LEFT,Node *RIGHT):left(LEFT),right(RIGHT){}
~BinNode(){delete left; delete right;} };
//------------------------------------------------------------------------------
class PlusNode: public BinNode{
public:
PlusNode(Node *LEFT,Node *RIGHT):BinNode(LEFT,RIGHT){}
double calc(){return left->calc()+right->calc();}
void print(){left->print(); std::cout<<"+("; right->print(); std::cout<<")";}
};
//------------------------------------------------------------------------------
class MinusNode: public BinNode{
public:
MinusNode(Node *LEFT,Node *RIGHT):BinNode(LEFT,RIGHT){}
double calc(){return left->calc()-right->calc();}
void print(){left->print(); std::cout<<"-("; right->print(); std::cout<<")";}
};
//------------------------------------------------------------------------------
class MultiplicationNode: public BinNode{
public:
MultiplicationNode(Node *LEFT,Node *RIGHT):BinNode(LEFT,RIGHT){}
double calc(){return left->calc()*right->calc();}
void print(){left->print(); std::cout<<"*("; right->print(); std::cout<<")";}



//------------------------------------------------------------------------------
class DivisionNode: public BinNode{
public:
DivisionNode(Node *LEFT,Node *RIGHT):BinNode(LEFT,RIGHT){}
double calc(){return left->calc()/right->calc();}
void print(){left->print(); std::cout<<"/("; right->print(); std::cout<<")";}
};
//------------------------------------------------------------------------------
class PowerNode: public BinNode{
public:
PowerNode(Node *LEFT,Node *RIGHT):BinNode(LEFT,RIGHT){}
double calc(){return pow(left->calc(),right->calc());}
void print(){left->print(); std::cout<<"^("; right->print(); std::cout<<")";}
};
//------------------------------------------------------------------------------
Node* postfixtree(const char *str){
Node *x1,*x2,*y;
int i=0;
stack <Node*> S;
while (str[i]!='\0'){
char ch=str[i];
switch(ch){
case '+': x2=S.pop(); x1=S.pop(); y=new PlusNode(x1,x2); break;
case '-': x2=S.pop(); x1=S.pop(); y=new MinusNode(x1,x2); break;
case '*': x2=S.pop(); x1=S.pop(); y=new MultiplicationNode(x1,x2); break;
case '/': x2=S.pop(); x1=S.pop(); y=new DivisionNode(x1,x2); break;
case '^': x2=S.pop(); x1=S.pop(); y=new PowerNode(x1,x2); break;
default : if((ch>=48)&&(ch<=57)){y=new NumNode(ch-48);}
else if(((ch>='a')&&(ch<='z'))||((ch>='A')&&(ch<='Z'))){y=new ParameterNode(ch);}
else{x1=S.pop(); y=new UnFuncNode(ch,x1);}}
S.push(y); ++i;} return S.pop();
}
//------------------------------------------------------------------------------
int main(int argc, char* argv[]){
Node *p1;
p1=postfixtree("AB+C*D-"); p1->print(); std::cout<<std::endl; double F=p1->calc();
std::cout<<"="<<F<<std::endl;
std::system("pause"); return 0;}
Сообщение
Это спам


 
#225
Павел 夜狩猟家 Соловьев 
27 мая 2009 в 23:37
// stack.h

#ifndef _STACK_
#define _STACK_

template <class T>
class stack{
T* datastore;
int first,maxsize;
public:
stack(unsigned int N=10):first(-1),maxsize(N){datastore=new T [N];}
~stack(){delete []datastore;}
T& top()const{return datastore[first];}
T pop(){return datastore[first--];}
void push(const T &X){
first++; if(first>=maxsize){int newsize=maxsize+1;
T* temp=new T[newsize];
for(int i=0;i<maxsize;++i){temp[i]=datastore[i];}
delete []datastore; datastore=temp;
maxsize=newsize;}
datastore[first]=X;}
};

#endif

Модератор: пользуйся кнопкой "код"

Это сообщение отредактировал(а) bsa - 30.5.2009, 21:13

andrew_121

Дата 30.5.2009, 18:48 (ссылка)

(нет голосов)

Загрузка ...

Кодофей

Профиль
Группа: Завсегдатай
Сообщений: 3448
Регистрация: 3.1.2008

Репутация: 0
Всего: 33

Цитата(Бонифаций @ 30.5.2009, 18:28

)

если посмотреть потроха, видно что этот rar.
А unzip на него ругается

Ну придрался же. smile

Я его 7zip-ом открыл, он и открылся. Остальное мне не интересно.

Цитата(OLESYAaa @ 30.5.2009, 18:42

)

я не блондинка(((блин

Сказано с сожалением?

Цитата(OLESYAaa @ 30.5.2009, 18:42

)

пары я посещала все, но НИКАК не дается. вот честно слово

Ну понял я что нужно сделать.

Ща подумаю...

--------------------

Удалил аккаунт. Прощайте!

OLESYAaa

Дата 30.5.2009, 18:50 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 4
Регистрация: 29.5.2009

Репутация: нет
Всего: нет

спасибо большое, я вон там еще прислала, нашла, я уже жить с такой ношей не могу((прям как заноза(((сидит в мозгу(((

andrew_121

Дата 30.5.2009, 18:55 (ссылка)

(нет голосов)

Загрузка ...

Кодофей

Профиль
Группа: Завсегдатай
Сообщений: 3448
Регистрация: 3.1.2008

Репутация: 0
Всего: 33

OLESYAaa, Ты опять код не вставила в тег! Щас админ ругаться будет! И ### твоему коду smile

Добавлено через 2 минуты и 17 секунд

Цитата(OLESYAaa @ 30.5.2009, 18:42

)

Сообщение
Это спам

#225
Павел 夜狩猟家 Соловьев
27 мая 2009 в 23:37

Любопытно... Это не ты случаем?

--------------------

Удалил аккаунт. Прощайте!

bsa

Дата 30.5.2009, 21:16 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 1
Всего: 196

OLESYAaa и andrew_121, переходите в приват, а то тема уже в оффтопик превратилась... А так как она изначально попадает в рязряд "сделайте за меня", то самое ей место в центре помощи. Поэтому переношу туда.

andrew_121 удачи smile

Это сообщение отредактировал(а) bsa - 30.5.2009, 21:17

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

bsa

Дата 30.5.2009, 21:18 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 1
Всего: 196

Для домашних заданий, курсовых, существует "Центр Помощи".

Тема перенесена!

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

Guedda

Дата 31.5.2009, 09:46 (ссылка)

(нет голосов)

Загрузка ...

Подрывник

Профиль
Группа: Завсегдатай
Сообщений: 3137
Регистрация: 27.12.2005
Где: Ростов-на-Дону

Репутация: 6
Всего: 78

M
Guedda

Модератор: Оффтоп удалил!

--------------------

Ll 2

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »