2014
02-26

# 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

#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