ZOJ 简单题集合（二）-阿里云开发者社区

对以下简单题，我同时给出一个我主观认为的难度值（0.1~1.0之间）。

(1). ZOJ 1072: Microprocessor Simulation. (Difficulty: 0.2)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1072

微处理器模拟，它含有两个累加器，代码和内存统一寻址，即冯诺依曼结构，比较简单。

ZOJ1072_cpp

#include <stdio.h>
#include <string.h>

char mem[256];    /* 256 words 内存 */
char A;            /* A 累加器 */
char B;            /* B 累加器 */

int PC;            /*程序计数器，code取址用*/

void Run()
{
int flag_STOP = 0;
int code, addr;
char tmp;
    PC = 0;

do
    {
/* reset PC */
if(PC >= 0xF0)
break;

/* 取指令 */
        code = mem[PC];
        ++PC;

switch(code)
        {
/* LD: Load accumulator A with the contents of memory 
               at the specified argument.*/
case 0: 
            addr = mem[PC] * 16 + mem[PC+1];
            PC += 2;
            A = mem[addr];
break;

/* ST: Write the contents of accumulator A to the memory
               location specified by the argument.*/
case 1:
            addr = mem[PC] * 16 + mem[PC+1];
            PC += 2;
            mem[addr] = A;
break;

/* SWP: Swap the contents of accumulators A and B. */
case 2:
            tmp = A;
            A = B;
            B = tmp;
break;

/* ADD: Add the contents of accumulators A and B. The 
               low word of the sum is stored in A, and the high 
               word in B. */
case 3:
            tmp = A + B;
            A = (tmp & 0x0F);
            B = (tmp >> 4);
break;

/* INC: Increment accumulator A. Overflow is allowed; 
               that is, incrementing F yields 0. */
case 4:
if(A == 0x0F) A = 0;
else A++;
break;

/* DEC: Decrement accumulator A. Underflow is allowed; 
               that is, decrementing 0 yields F.*/
case 5:
if(A == 0) A = 0x0F;
else A--;
break;

/* BZ: If accumulator A is zero, the next command to be 
               executed is at the location specified by the argument. 
               If A is not zero, the argument is ignored and nothing 
               happens. */
case 6:
            addr = mem[PC] * 16 + mem[PC+1];
            PC += 2;
if(A == 0)
            {
                PC = addr;
            }
break;

/* BR: The next command to be executed is at the location 
               specified by the argument. */
case 7:
            addr = mem[PC] * 16 + mem[PC+1];
            PC = addr;
break;

/* STP: Stop execution of the program. */
case 8:
            flag_STOP = 1;
break;
        }
    }
while(!flag_STOP);
}

char CharToNum(char c)
{
if(c >= '0' && c <= '9') return (c - '0');
else return (c - 'A' + 10);
}

char NumToChar(char c)
{
if(c >= 0 && c <= 9) return (c + '0');
else return (c + 'A' - 10);
}

int main(int argc, char* argv[])
{
char line[264];
int i, j;

do
    {
/* 读取一次完整的输入 */
        i = 0;
do
        {
            gets(line);
for(j = 0; j < strlen(line); j++)
            {
                mem[i] = CharToNum(line[j]);
                i++;
            }
        }
while(i < 256);

/*结束输入的标志*/
if(mem[0] == 8)
break;

        Run();

/* output */
for(j = 0; j < 256; j++)
        {
            printf("%c", NumToChar(mem[j]));
        }
        printf("\n");
    }
while(1);
return 0;
}

(2). ZOJ 1414: Num Steps. (Difficulty: 0.2)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1414

一个网格如下图所示，给出一个坐标（x，y），要求输出其数字，如果没有数字则输出 "No Number”;

ZOJ1414_cpp

#include <stdio.h>
int main(int argc, char* argv[])
{
int count, i;
int x, y, num;
    scanf("%d", &count);
for(i = 0; i < count; i++)
    {
        scanf("%d %d", &x, &y);
if(x - y == 0 || x - y == 2)
        {
            num = ((x >> 1) << 2) + (x & 1) - (x - y);
            printf("%d\n", num);
        }
else
            printf("No Number\n");
    }
return 0;
}

(3). ZOJ 1170: String Matching. (0.3)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1170

求出两个字符串的相似值（一个化简后的分数）。

ZOJ1170_cpp

#include <stdio.h>
#include <string.h>

char szLine[512];

//得到两个字符串的相同字符个数
int SameLetterCount(const char* s1, const char* s2)
{
int count = 0;
const char *p1 = s1;
const char *p2 = s2;
while(*p1 && *p2)
    {
if(*p1 == *p2) count++;
        ++p1;
        ++p2;
    }
return count;
}

//此方法的时间复杂度应该是O(n ^ 2)
void GetAppx(const char* s1, const char* s2, int* pAppx, int* pTotalLen)
{
int appx = 0, tmp_appx = 0, index;

int len1 = strlen(s1);
int len2 = strlen(s2);

    *pTotalLen = len1 + len2;

if(strcmp(s1, s2) == 0)
    {
        *pAppx = *pTotalLen;
return;
    }

for(index = -(len2 - 1); index <= len1 - 1; ++index)
    {
if(index <= 0)
            tmp_appx = SameLetterCount(s1, s2 - index);
else
            tmp_appx = SameLetterCount(s2, s1 + index);

if(tmp_appx > appx)
            appx = tmp_appx;
    }
    *pAppx = appx * 2;
}

// 辗转相除法，求最大公约数
int GetGcd(int a, int b)
{
int tmp;
while(b > 0)
    {
        tmp = a % b;
        a = b;
        b = tmp;
    }
return a; 
}

int main(int argc, char* argv[])
{
char* pBlank = NULL;
int totalLen = 0, appx = 0, gcd = 0;
while( 1 )
    {
        gets(szLine);
if(strcmp(szLine, "-1") == 0)
break;

//在空格处截断字符串
         pBlank = strchr(szLine, ' ');
        *pBlank = 0; 

        GetAppx(szLine, pBlank + 1, &appx, &totalLen);

if(appx == 0)
            printf("appx(%s,%s) = 0\n", szLine, pBlank + 1);
else if(appx == totalLen)
            printf("appx(%s,%s) = 1\n", szLine, pBlank + 1);
else
        {
//化简分数
              gcd = GetGcd(totalLen, appx);
            totalLen /= gcd;
            appx /= gcd;

            printf("appx(%s,%s) = %d/%d\n", 
                szLine, pBlank + 1, appx, totalLen);
        }
    }
return 0;
}

(4). ZOJ 1240: IBM Minus One (0.1)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1240

超级简单，把字符串中每个字符用其字母序后面的字符替换。

ZOJ1240_cpp

#include <stdio.h>
#include <string.h>

//把每个字母向后旋转一格，c = c + 1, Z->A
void Transfer(char* s)
{
char* p = s;
while(*p)
    {
if(*p == 'Z') *p = 'A';
else *p = *p + 1;
        ++p;
    }
}

int main(int argc, char* argv[])
{
char line[56];
int count = 0, i;

    scanf("%d\n", &count);
for(i = 0; i < count; i++)
    {
        gets(line);
        Transfer(line);
        printf("String #%d\n%s\n\n", i+1, line);
    }
return 0;
}

(5) ZOJ 1295: Reverse Text (0.1)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1295

反转字符串，即 CRT 中的 strrev。

ZOJ1295_cpp

#include <string.h>
#include <stdio.h>

void reverse(char* str)
{
char tmp;
int left = 0;
int right = strlen(str) - 1;
while(left < right)
   {
       tmp = str[left];
       str[left] = str[right];
       str[right] = tmp;
       ++left;
       --right;
   }
}

int main(int argc, char* argv[])
{
char str[256];
int n, i;
    scanf("%d\n", &n);
for(i=0; i<n; i++)
    {
        gets(str);
/*scanf("%s", str);*/
        reverse(str);
        printf("%s\n", str);
    }
return 0;
}

(6). ZOJ 1383: Binary Numbers (0.2)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1383

输出一个数字二进制表示中 1 所在的位。（注意输出格式）

ZOJ1383_cpp

#include <stdio.h>

int main(int argc, char* argv[])
{
int count = 0, i, num, iDigit;
//是否需要在该位前输出一个空格
    int bNeedSpace;

    scanf("%d", &count);
for(i = 0; i < count; i++)
    {
        scanf("%d", &num);
        iDigit = 0;
        bNeedSpace = 0;
while(num != 0)
        {
if(num & 1)
            {
if(bNeedSpace) printf(" ");
                printf("%d", iDigit);
                bNeedSpace = 1;
            }
            num = (num >> 1);
            ++iDigit;
        }
if(i < count - 1)
            printf("\n");
    }
return 0;
}

(7). ZOJ 1814: Candy Sharing Game (0.2)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1814

分糖果游戏，学生围成一圈，每次把手里的一半糖果分给右侧的人，如果任何人糖果为奇数，则再分给他一颗，直到所有人持有糖果数相同。模拟法。

ZOJ1814_cpp

#include <stdio.h>

//students: 每个学生持有的糖果数（逆时针方向）
//n: 学生个数
//rounds：游戏轮次
//candy：游戏结束时每个学生手里的糖果数
void Play(int* students, int n, int* rounds, int* candy)
{
int i, students0, tmp_candy, left_candy;
int bGameOver;
    *rounds = 0;
while(1)
    {
        students0 = students[0];
        bGameOver = 1;
for(i = 0; i < n; i++)
        {
            left_candy = (i == (n-1))? students0 : students[i+1];
            students[i] = (students[i] + left_candy)/2;
//如果是奇数，立即再给他一个糖果
              if(students[i] & 1)
                students[i]++;

if(i == 0)
                tmp_candy = students[0]; //初始化
              else if(bGameOver && students[i] != tmp_candy)
            {
                bGameOver = 0;
            }
        }
        (*rounds)++;
if(bGameOver) break;
    }

//最终结果
    *candy = students[0];
}

int main(int argc, char* argv[])
{
int students[1024];
int n, i;
int rounds, candy;

while(1)
    {
        scanf("%d", &n);
if(n == 0) break;
for(i=0; i<n; i++)
            scanf("%d", (students + i));

        Play(students, n, &rounds, &candy);
        printf("%d %d\n", rounds, candy);
    }
return 0;
}

(8). ZOJ 2680: Clock (0.3)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2680
给出 5 个时刻，按时钟的时针，分针夹角从小到大排序，输出中间的时刻。显然，整数分钟（不考虑秒）时刻，时针分针的夹角是 0.5 角度的整数倍，因此为回避浮点数，采用 0.5 度为指针夹角的基本单位（一个圆周为 360 度）。由于需要输出的只是排序后的中间元素，排序时只要排好一半即可。

ZOJ2680

#include <stdio.h>

typedef struct tagTime
{
int angle; //夹角以0.5度为单位
     int hour;
int minute;
} TIME;

typedef TIME Item;

Item items[5];

int lessthan(Item t1, Item t2)
{
if     (t1.angle < t2.angle) return 1;
else if(t1.angle > t2.angle) return 0;
else if(t1.hour < t2.hour) return 1;
else if(t1.hour > t2.hour) return 0;
else if(t1.minute < t2.minute) return 1;
else return 0;
}


/*交换a[]的i，j项*/
void exchange(Item a[], int i, int j)
{
int _angle = a[i].angle;
int _hour = a[i].hour;
int _minute = a[i].minute;

    a[i].angle = a[j].angle;
    a[i].hour = a[j].hour;
    a[i].minute = a[j].minute;

    a[j].angle = _angle;
    a[j].hour = _hour;
    a[j].minute = _minute;
}


/*选择排序*/
// stopIndex: 当排序到索引stopIndex，即可停止排序
void SelectionSort(Item a[], int left, int right, int stopIndex)
{
int i, j, min;
//for(i = left; i < right; i++) //完整排序
    for(i = left; i <= stopIndex; i++)
    {
        min = i;
for(j = i + 1; j <= right; j++)
if(lessthan(a[j], a[min])) min = j;
        exchange(a, i, min);
    }
}

//以 0.5度 为单位（eg. 180 units = 90 度，720 units = 360 度）
int GetAngle(int hour, int minute)
{
int hour2 = (hour > 12) ? (hour - 12) : hour;
int a1 = 60 * hour2 + minute;
int a2 = minute * 12;
int result = a2 - a1;
if(result < 0)
        result = -result;
if(result > 360)
        result = 720 - result;
return result;
}

int main(int argc, char* argv[])
{
int i, j, count;
char line[48];
    scanf("%d\n", &count);
for(i = 0; i < count; i++)
    {
        gets(line);
for(j = 0; j < 5; j++)
        {
            items[j].hour = ( line[j*6] - '0' ) * 10
                + ( line[j*6+1] - '0' );
            items[j].minute = ( line[j*6 + 3] - '0' ) * 10
                + ( line[j*6+4] - '0' );
            items[j].angle = GetAngle(items[j].hour, items[j].minute);
        }
        SelectionSort(items, 0, 4, 2);
        printf("%02d:%02d\n", items[2].hour, items[2].minute);
    }
return 0;
}

(9). ZOJ 3191: Strange Clock (0.2)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3191

给出时针的角度，输出该时刻处于几点钟。

ZOJ3191_cpp

#include <stdio.h>

int main(int argc, char* argv[])
{
int hourBig, hourSmall;
int bExactly; //注意 gcc 没有定义过 bool 类型
    int degree;

while( 1 )
    {
        scanf("%d", &degree);
if(degree == -1) break;

        bExactly = (degree - (degree / 30 * 30) == 0);
        hourBig = (degree < 120 ? 3 : 15) - (degree / 30);
        hourSmall = (hourBig == 0) ? 11 : (hourBig - 1);

if(bExactly)
            printf("Exactly %d o'clock\n", hourBig);
else
            printf("Between %d o'clock and %d o'clock\n", hourSmall, hourBig);
    }
return 0;
}

(10). ZOJ 3247: Hello World (0.3)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3247

给出一个点阵，要求输出字符图形（每一行输入由 5 个字节组成，代表一个字符，每个字节代表该字符的一列，即每个字符实际上7 * 5 像素，注意行和 bit 之间的对应关系，低位对应的是上方像素，高位对应下方像素，所有字节的最高位为 0，表示最后一行没有任何像素，注意最后一行不能输出一长串空格，而是要输出成空行即直接换行，否则将导致 PE），备注：可使用 strtol 把16进制字符串转换成整数。

ZOJ3247_cpp

#include <stdio.h>

char map[80][5];

char CharToInt(char c)
{
if(c >= '0' && c <= '9')
return (c - '0');
else if(c >= 'A' && c <= 'F')
return (c + 10 - 'A');
else
return 0;
}

int main(int argc, char* argv[])
{
char line[24];
int test_count, char_count, i, j, k, col;
    scanf("%d", &test_count);
for(i = 1; i <= test_count; i++)
    {
        scanf("%d\n", &char_count);
for(j = 0; j < char_count; j++)
        {
            gets(line);
for(k = 0; k < 5; k++)
            {
                map[j][k] = CharToInt( line[k*3] ) * 16 
                    + CharToInt( line[k*3+1] );
            }
        }

//output the string
        printf("Case %d:\n\n", i);

//j: rows index
        for(j = 0; j < 8; j++)
        {
if(j < 7)
            {
for(k = 0; k < char_count; k++)
                {
//输出一个字符的某一行（五列）
                        for(col = 0; col < 5; col++)
                     {
if( map[k][col] & (1 << j) )
                            printf("#");
else
                            printf(" ");
                      }
//字符和字符之间的空列
                         if(k < char_count - 1)
                         printf(" ");
                 }
            }
//一行结束，换行
              printf("\n");
        }
    }
return 0;
}

(11). ZOJ 3322: Who is older ? (0.1)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3322

给出两个人的生日，比较年龄谁大，超级简单，直接比较字符串即可。

ZOJ3322_cpp

#include <stdio.h>
#include <string.h>

int main(int argc, char* argv[])
{
char line[36];
int n, i, result;
    scanf("%d\n", &n);
for(i = 0; i < n; i++)
    {
        gets(line);
        line[10] = 0;
        result = strcmp(line, line + 11);
if(result < 0)
            printf("javaman\n");
else if(result > 0)
            printf("cpcs\n");
else
            printf("same\n");
    }
return 0;
}

(12). ZOJ 3487: Ordinal Numbers (0.1)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3487

给出一个数字，根据规则，给出其序数后缀表示。

ZOJ3487_cpp

#include <stdio.h>
#include <string.h>

void GetPostfix(const char* line, char* postfix)
{
int len = strlen(line);
//十位上的字符
    char c = '0';
if(len > 1)
        c = line[len-2];

//If the tens digit of a number is 1, then write
//"th" after the number. For example: 13th, 19th, 112th, 9311th. 
    if(c == '1')
    {
        strcpy(postfix, "th");
    }
else
    {
//If the tens digit is not equal to 1, then use
//"st" if the units digit is 1, 
//"nd" if the units digit is 2, 
//"rd" if the units digit is 3, and 
//"th" otherwise: 
//For example: 2nd, 7th, 20th, 23rd, 52nd, 135th, 301st. 

switch(line[len-1])
        {
case '1': strcpy(postfix, "st"); break;
case '2': strcpy(postfix, "nd"); break;
case '3': strcpy(postfix, "rd"); break;
default:  strcpy(postfix, "th"); break;
        }
    }
}

int main(int argc, char* argv[])
{
int count = 0, i;
char line[48], postfix[4];

    scanf("%d\n", &count);
for(i = 0; i < count; i++)
    {
        gets(line);
        GetPostfix(line, postfix);
        printf("%s%s\n", line, postfix);
    }
return 0;
}

(13). ZOJ 3542: Hexadecimal View (0.1)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3542

给出一行字符串（全部是可打印字符），输出 16 进制视图。备注：字符大小写的互相转换也可使用 touppder / tolower 。

ZOJ3542_cpp

#include <stdio.h>
#include <string.h>

void OutputHexView(char* s)
{
char *p = s;
int i, linenum = 0;
char line[16];
int len = strlen(s);
int linecount = (len + 15)/16;  //需要打印的总行数
for(linenum = 0; linenum < linecount; ++linenum)
    {
        memset(line, 0, 16);
        strncpy(line, p, 16);
        p += 16;
        printf("%04x: ", (linenum << 4) & 0xffff);
for(i = 0; i < 16; i++)
        {
if(line[i] == 0)
                printf("  ");   //没有字符（最后一行的 padding 部分）
else
                printf("%02x", line[i]);

if(i & 1) 
                printf(" ");   //每两个字符之间有一个空格间隔
        }
for(i = 0; i < 16; i++)
        {
if(line[i] == 0)
            {
break;
            }
else if(line[i] >= 'a' && line[i] <= 'z') // islower( line[i] )
            {
                printf("%c", line[i] + 'A' - 'a');    // toupper( line[i] )
            }
else if(line[i] >= 'A' && line[i] <= 'Z')
            {
                printf("%c", line[i] + 'a' - 'A');   // tolower;
            }
else
            {
                printf("%c", line[i]);
            }
        }
        printf("\n");
    }
}

int main(int argc, char* argv[])
{
char line[4100];
while( gets(line) != NULL )
    {
        OutputHexView(line);
    }
return 0;
}

(14). ZOJ 3317: Murder in Restaurant (0.3)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3317

给出一个旅馆的入住信息表，客人数和房间数，给出每个客人的试图入住日期和离店日期（都用整数表示），尝试给客人分配一个最小房号（从1开始计数）的房间，要求输出每个客人的入住房号，如果该客人来时没有房间则输出 0。

解法：把客人按照入住时间升序排序，然后依次分配房间号。（有些类似贪心法中的申请会议室）

ZOJ3317_cpp

#include <stdio.h>

int Rooms_Leave[100];      /* 每个元素表示第 i 个房间退房的日期 */
int Renters_RoomNo[100];   /* 每个元素分配给第 i 个客人的房间号 */

typedef struct tagRENTER
{
int index;     //客人索引（0 base）
     int EnterDate; //入住日期
     int LeaveDate; //离店日期
} RENTER, *PRENTER;

typedef RENTER Item;

Item items[100];

int less_than(Item t1, Item t2)
{
if (t1.EnterDate < t2.EnterDate) return 1;
else return 0;
}


/*交换a[]的i，j项*/
void exchange(Item a[], int i, int j)
{
if(i != j)
    {
int _index = a[i].index;
int _EnterDate = a[i].EnterDate;
int _LeaveDate = a[i].LeaveDate;

        a[i].index = a[j].index;
        a[i].EnterDate = a[j].EnterDate;
        a[i].LeaveDate = a[j].LeaveDate;

        a[j].index = _index;
        a[j].EnterDate = _EnterDate;
        a[j].LeaveDate = _LeaveDate;
    }
}

/*选择排序*/
void SelectionSort(Item a[], int left, int right)
{
int i, j, min;
for(i = left; i < right; i++)
    {
        min = i;
for(j = i + 1; j <= right; j++)
if(less_than(a[j], a[min])) min = j;
        exchange(a, i, min);
    }
}


int main(int argc, char* argv[])
{
int renter_count, room_count, i, j;

while( 1 )
    {
        scanf("%d %d", &renter_count, &room_count);

if(renter_count == 0)
break;

for(i = 0; i < renter_count; i++)
        {
            Rooms_Leave[i] = 0;
            Renters_RoomNo[i] = 0;
            items[i].index = i;
            scanf("%d %d", &items[i].EnterDate, &items[i].LeaveDate);
        }

/* 给每个客人分配房间 */
        SelectionSort(items, 0, renter_count - 1);
for(i = 0; i < renter_count; i++)
        {
for(j = 0; j < room_count; j++)
            {
if(Rooms_Leave[j] <= items[i].EnterDate)
                {
                    Rooms_Leave[j] = items[i].LeaveDate;
                    Renters_RoomNo[ items[i].index ] = j + 1;
break;
                }
            }
        }

/* output result */
for(i = 0; i < renter_count; i++)
        {
            printf("%d\n", Renters_RoomNo[i]);
        }
    }
return 0;
}

(15). ZOJ 2850: Beautiful Meadow ( 0.1 )

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2850

给出一个 N * M 的网格，每个 cell 的值是 0 或 1。如果所有 cell 都是1，或有任何为 0 的 cell 相邻（即共享某条边），则输出No，否则输出Yes。

zoj2850_cpp

#include <stdio.h>

int main(int argc, char* argv[])
{
int row, col, i, j, tmp, sum;
int bMowedAdjacent;
char map[100][100];
while(1)
    {
        scanf("%d %d", &row, &col);
if(row == 0)
break;

        bMowedAdjacent = 0;
        sum = 0;
for(i = 0; i < row; i++)
        {
for(j = 0; j < col; j++)
            {
                scanf("%d", &tmp);
                map[i][j] = tmp;
if(tmp == 0)
                {
if(j > 0 && map[i][j-1] == 0)
                        bMowedAdjacent = 1;
else if(i > 0 && map[i-1][j] == 0)
                        bMowedAdjacent = 1;
                }
else
                    sum += tmp;
            }
        }
if(bMowedAdjacent || sum == row * col) printf("No\n");
else printf("Yes\n");
    }
return 0;
}

(16). ZOJ 1094: Matrix Chain Multiplication ( 0.3 )

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1094

虽然题目是算法经典命题-矩阵乘法链，但是此题目考察的绝不是动态规划（DP），而是给出一个矩阵乘法加括号的表达式，求该方案所需的乘法运算数。如果矩阵乘法不相容，则输出 "error"。此题目的输入非常标准，无需考虑表达式的括号不匹配等问题。也无需考虑例如 "ABC" 这种没有加括号的表达式（输入一定给出的是 "((AB)C)" ）。如果是只有单个矩阵，则一定没有括号。这种输入的标准化使我们无需检测特殊情况（例如 "(A)", "ABC", ")AB" 等），可以仅仅用表达式中的括号去推动表达式的解析。

解法是：准备两个辅助栈，一个装入矩阵信息（操作数），一个装入括号（由于输入表达式一定括号匹配，因此第二个辅助栈实际上不需要，但为了保持逻辑完整性依然保留），每次遇到“）”符号，则从操作数栈中弹出两个矩阵，如果相容，则累加这两个矩阵相乘的代价，然后把结果信息 (row, col) 再次入栈。

zoj1094_cpp

#include <stdio.h>

typedef struct _tagMatrixInfo
{
int row;
int col;
} MatrixInfo;

MatrixInfo matrix[26];

/* szExpression: 形如"(A(BC))"; 返回值：乘法次数，-1 代表不相容 */
int GetResult(char* szExpression)
{
char *p = szExpression;
char c;

char brackets[512];   /* 括号的栈 */
int pBrackets = -1;   /* 栈顶指针 */

    MatrixInfo nums[512]; /* 操作数栈 */
int pNums = -1;       /* 栈顶指针 */

int row0, col0, row1, col1;
int count = 0;        /* 返回的结果：总乘法次数 */
while(*p)
    {
        c = *p;
        ++p;
if(c >= 'A' && c <= 'Z') /* push in stack */
        {
            ++pNums;
            nums[pNums].row = matrix[c-'A'].row;
            nums[pNums].col = matrix[c-'A'].col;
        }
else if(c == '(')
        {
            brackets[++pBrackets] = c;
        }
else if(c == ')')
        {
/* 从栈中弹出两个操作数 */
            row0 = nums[pNums - 1].row;
            col0 = nums[pNums - 1].col;
            row1 = nums[pNums].row;
            col1 = nums[pNums].col;
            pNums -= 2;
            pBrackets--; /* 弹出一个'(' */

/* 两个操作数是否相容？ */
if(col0 != row1)
return -1;

            count += row0 * col0 * col1;

/* 结果信息 push 到操作数栈中 */
            ++pNums;
            nums[pNums].row = row0;
            nums[pNums].col = col1;
        }
    }
return count;
}
int main(int argc, char* argv[])
{
int n, i, result;
char cNum, line[1024];
    scanf("%d\n", &n);
for(i = 0; i < n; i++)
    {
        scanf("%c ", &cNum);
        scanf("%d %d\n", &matrix[cNum-'A'].row, &matrix[cNum-'A'].col);
    }
while(gets(line) != NULL)
    {
        result = GetResult(line);
if(result < 0) printf("error\n");
else printf("%d\n", result);
    }
return 0;
}

ZOJ 简单题集合（二）

热门文章

最新文章

相关电子书