首页 > ACM题库 > HDU-杭电 > HDU 3000-A Simple Language-栈-[解题报告]HOJ
2014
02-26

HDU 3000-A Simple Language-栈-[解题报告]HOJ

A Simple Language

问题描述 :

Professor X teaches the C Programming language in college, but he finds it’s too hard for his students and only a few students can pass the exam. So, he decide to invent a new language to reduce the burden on students.This new language only support four data type, but the syntax is an strict subset of C. It only support assignment operation, brackets operation , addition , subtration, multiplication and division between variables and numbers. The priority of operations is the same as C.

In order to void the problem of forgetting the eliminator “;”, this new language allow to omit it.

The variable naming rules is the same as C.

Comments is not allowed in this language.

Now Prof.X need to impelment this language, and the variable part is done by himself. Now Prof.X need you, a execllent ACM coder’s help: Given a section of this language’s code, please calculate it’s return value.

输入:

The input contains many lines, each line is a section of codes written in the language described above, you can assume that all variables have been declared as int and have been set to 0 initially.

输出:

The input contains many lines, each line is a section of codes written in the language described above, you can assume that all variables have been declared as int and have been set to 0 initially.

样例输入:

a=3
a+b
a=a*(b+2)+c;
a+b
a/4
_hello=2*a;

样例输出:

3
3
6
6
1
12

这题和一般的表达式运算有些不同,要处理等号这种运算。。

其实等号运算的优先级可以看成是除(外最低的。。。

具体的运算符优先级可以去查看c++之类的书籍,参考一下就ok了。。

另外变量值的储存可以用map来实现。。。

#include <iostream>
#include <string>
#include <map>
using namespace std;
#define STRLEN 1000
//获取优先级
int GetPriority(char oper)
{
switch (oper)
{
case '(':
   return 0;
   break;
case '=':
   return 1;
   break;
case '+':
   return 2;
   break;
case '-':
   return 2;
   break;
case '*':
   return 3;
   break;
case '/':
   return 3;
   break;
}
}
//判断是否应该计算
bool IsCalc(char inStack, char outStack)
{
return GetPriority(inStack)>=GetPriority(outStack);
}
//分词标志
bool IsSplit(char c)
{
if (c == '+' || 
   c == '-' ||
   c == '*' ||
   c == '/' ||
   c == '(' ||
   c == ')' ||
   c == '=')
   return true;
else
   return false;
}
//true is oper, false is num
bool GetNext(char STR[], int &s, char ans[])
{
int i = s, j = 0;
int len = strlen(STR);
bool flag = false;
for (; i<len; i++)
{
   if (IsSplit(STR[i]))
   {
    if (j == 0)
    {
     ans[j++] = STR[i++];
     flag = true;
    }
    break;
   } else {
    ans[j++] = STR[i];
   }
}
ans[j] = 0x00;
s = i;
return flag;
}
//判断是否是数字
bool IsNum(char s[])
{
if (s[0] >= '0' && s[0] <= '9' || s[0] == '-')
   return true;
else
   return false;
}
int Calc(int a, int b, char oper)
{
switch(oper)
{
case '+':
   return a+b;
   break;
case '-':
   return a-b;
   break;
case '*':
   return a*b;
   break;
case '/':
   return a/b;
   break;
}
}
void GetTrueStr(char str[])
{
int len = strlen(str);
int i;
for (i = len-1; i>=0; i--)
   if (str[i] == ';')
    str[i] = 0x00;
   else
    break;
}
int main()
{
char STR[STRLEN];
char OperStack[STRLEN];
char NumStack[STRLEN][100];
char ans[STRLEN];
char PutToNumStack[STRLEN];
int OperTop, NumTop, StrPos;
//从符号栈中取出的元素
char cTopOper;
//从数字栈中取出的元素。
char a[STRLEN], b[STRLEN];
//计算用到的,c为结果
int NumA, NumB, NumC;
//int NumC to string sNumC
char sNumC[STRLEN];
//MAP
map<string, int> t_map;
int len;
bool isFuShu;
while (cin.getline(&STR[1], STRLEN))
{
   //memset
   memset(OperStack, 0, sizeof(OperStack));
   memset(NumStack, 0, sizeof(NumStack));
   memset(ans, 0, sizeof(ans));
   isFuShu = false;
   //前加(
   STR[0] = '(';
   //去多余的;
   GetTrueStr(STR);
   len = strlen(STR);
   //最后加)
   STR[len++] = ')';
   STR[len] = 0x00;
   //将原来的20+20的表达式串构造成(20+20)这种形式

   StrPos = OperTop = NumTop = 0;
   while (StrPos < len)
   {
    //如果是操作符
    if (GetNext(STR, StrPos, ans))
    {
     //如果此数为负数,也就是(-100)这样的形式
     if (ans[0] == '-' && STR[StrPos-1] == '(')
     {
      isFuShu = true;
      continue;
     }
     //如果为(则入栈
     if (ans[0] == '(')
     {
      OperStack[OperTop++] = ans[0];
     }
     //如果为右括号,则计算到左括号为止
     else if (ans[0] == ')')
     {
      //取栈顶符号
      while ((cTopOper = OperStack[--OperTop]) != '(')
      {
       //如果符号为等号,则进行赋值操作
       if (cTopOper == '=')
       {
        strcpy(b, NumStack[--NumTop]);
        strcpy(a, NumStack[--NumTop]);
        if (IsNum(b))
         NumB = atoi(b);
        else
         NumB = t_map[b];
        t_map[a] = NumB;
        //结果压回栈
        strcpy(NumStack[NumTop++], b);
       } else {
        strcpy(b, NumStack[--NumTop]);
        strcpy(a, NumStack[--NumTop]);
        //判断是否数字,如果不是数字就从map中取值
        if (IsNum(b))
         NumB = atoi(b);
        else
         NumB = t_map[b];
        if (IsNum(a))
         NumA = atoi(a);
        else
         NumA = t_map[a];
        //进行运算
        NumC = Calc(NumA, NumB, cTopOper);
        sprintf(sNumC, "%d", NumC);
        //结果压回栈
        strcpy(NumStack[NumTop++], sNumC);
       }
      }
     //如果是=号,则入栈
     } else if (ans[0] == '=')
     {
      OperStack[OperTop++] = ans[0];
     //如果是其他符号,则进行优先级判断
     } else {
      //如果栈顶符号优先级大于等于外面的,那么进行计算
      while (IsCalc(OperStack[OperTop-1], ans[0]))
      {
       strcpy(b, NumStack[--NumTop]);
       strcpy(a, NumStack[--NumTop]);
       //判断是否数字,如果不是数字就从map中取值
       if (IsNum(b))
        NumB = atoi(b);
       else
        NumB = t_map[b];
       if (IsNum(a))
        NumA = atoi(a);
       else
        NumA = t_map[a];
       //取出符号栈第一个符号
       cTopOper = OperStack[--OperTop];
       //进行运算
       NumC = Calc(NumA, NumB, cTopOper);
       sprintf(sNumC, "%d", NumC);
       //结果压回栈
       strcpy(NumStack[NumTop++], sNumC);
      }
      //如果外面的符号优先级大于栈顶的,则压入栈
      if (IsCalc(OperStack[OperTop-1], ans[0]) == false)
       OperStack[OperTop++] = ans[0];
     }
    } else {
    //如果不是,则把操作数入栈,这里要处理负数
     if (isFuShu)
     {
      PutToNumStack[0] = '-';
      strcpy(&PutToNumStack[1], ans);
     } else {
      strcpy(PutToNumStack, ans);
     }
     strcpy(NumStack[NumTop++], PutToNumStack);
    }
    isFuShu = false;
   }
   strcpy(a, NumStack[--NumTop]);
   if (IsNum(a))
    NumA = atoi(a);
   else
    NumA = t_map[a];
   printf("%d\n", NumA);
}
return 0;
}

,
  1. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  2. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept