[Intermediate] Calculator

逆波兰式又叫做后缀表达式。在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，这种表示法也称为中缀表示。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法，按此方法，每一运算符都置于其运算对象之后，故称为后缀表达式。

正常的表达式 逆波兰式
a+b ---> a,b,+
a+(b-c) ---> a,b,c,-,+
a+(b-c)*d ---> a,b,c,-,d,*,+
a+d*(b-c)--->a,d,b,c,-,*,+
a=1+3 ---> a=1,3 +
http=(smtp+http+telnet)/1024 写成什么呢？
http,smtp,http,+,telnet,+,1024,/,=
用途
逆波兰表达式是一种十分有用的表达式，它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式。例如(a+b)*(c+d)转换为ab+cd+*
优势
它的优势在于只用两种简单操作，入栈和出栈就可以搞定任何普通表达式的运算。其运算方式如下：
如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。
算法：
中缀表达式转后缀表达式的方法：
1.遇到操作数：直接输出（添加到后缀表达式中）
2.栈为空时，遇到运算符，直接入栈
3.遇到左括号：将其入栈
4.遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出。
5.遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈
6.最终将栈中的元素依次出栈，输出。
例如
a+b*c+(d*e+f)*g ----> abc*+de*f+g*+

遇到a:直接输出：
后缀表达式：a
堆栈：空

遇到+:堆栈：空，所以+入栈
后缀表达式：a
堆栈：+
遇到b: 直接输出
后缀表达式：ab
堆栈：+
遇到*：堆栈非空，但是+的优先级不高于*，所以*入栈
后缀表达式： ab
堆栈：*+
遇到c:直接输出
后缀表达式：abc
堆栈：*+
遇到+：堆栈非空,堆栈中的*优先级大于+，输出并出栈，堆栈中的+优先级等于+，输出并出栈，然后再将该运算符(+)入栈
后缀表达式：abc*+
堆栈：+
遇到(：直接入栈
后缀表达式：abc*+
堆栈：(+
遇到d：输出
后缀表达式：abc*+d
堆栈：(+
遇到*：堆栈非空，堆栈中的(优先级小于*，所以不出栈
后缀表达式：abc*+d
堆栈：*(+
遇到e：输出
后缀表达式：abc*+de
堆栈：*(+
遇到+：由于*的优先级大于+，输出并出栈，但是(的优先级低于+，所以将*出栈，+入栈
后缀表达式：abc*+de*
堆栈：+(+
遇到f：输出
后缀表达式：abc*+de*f
堆栈：+(+
遇到)：执行出栈并输出元素，直到弹出左括号，所括号不输出
后缀表达式：abc*+de*f+
堆栈：+
遇到*：堆栈为空，入栈
后缀表达式： abc*+de*f+
堆栈：*+
遇到g：输出
后缀表达式：abc*+de*f+g
堆栈：*+
遇到中缀表达式结束：弹出所有的运算符并输出
后缀表达式：abc*+de*f+g*+
堆栈：空

[求值]
逆波兰表达式是一种利用栈来进行运算的数学表达式。

以一个表达式 1 + 2 * 3 为例。以顺序方式输入这个表达式，计算机首先
需要解析这个表达式，然后递归的求值。比如从左起进行顺序解析，得到
一个符号树：
   +
  / \
 1   *
    / \
   2   3
计算机会递归的从叶子开始求值，最后回到根，得出结果。所以对于一个
比较复杂的表达式，树可能会很深，而且递归的过程将会消耗大量的内存,
由于有解析和运算两个过程，时间开销也不理想。

如果将上式改为逆波兰表达式： 3 2 * 1 +
那么就能实现“在线处理”。在线处理是这类问题在计算机中最快的算法。
还是从左侧开始，扫描这个表达式。扫描到第一项，为一个操作数，那么
可以把这个数压栈，然后继续扫面。
top:
 3

第二项还是一个操作数，同样的压栈继续。
top:
 2
 3

到第三项，得到一个双目运算符，这时候计算机就从操作数栈中弹出两个
数作为运算符的两个参数，然后进行运算，并将结果再压回操作数栈。
top:
 6

接着第四项，一个操作数，压栈。第五项，又是一个双目运算符，那么弹
出两个操作数进行运算，把结果压栈。
top:
 1
 6

到此，这个表达式就扫描结束了，操作数栈中最后会剩下表达式的运算结果。
top:
 7

不需要两次操作，只要从头扫描到尾就能求出结果，也不需要递归，只需
要一个很小的栈就可以。所以逆波兰表达式算法取得了时间复杂度和空间
复杂度上的双重优势。

并且：
   从左到右扫描，有运算符就运算，对于复杂的表达式，不容易出错；
   栈可以自动的记录中间结果；
   机器只需要维护一个操作数堆栈，栈中只有操作数和结果

所以在机器上实现起来非常的方便。早期，处理器性能比较弱的时候，使
用这种方式就可以在性能不足的机器上实现任意复杂度的表达式运算。很
棒吧。


      引刀成一块，不负少年头。

[Problem]
Create a program which converts a character string of
calculation formula to a postfix expression and calcu
lates it.

For example, a character string “3+(4+5)*6+7” can be
converted to a postfix expression "345+6*+7+".
The calculation should yield 64.
The operators used in the formula are ‘+’ and ‘*’. Pa
rentheses can be used in the formula. The operands ar
e the integers between 0 ~ 9. The parentheses are alw
ays paired properly.
 
[Input]
The first line of the input file provides the length
of the test case. The test cases are given in the nex
t lines. Total of 10 test cases are given.

10
113
(9+(5*2+1)+(3*3*7*6*9*1*7+1+8*6+6*1*1*5*2)*4*7+4*3*8*2*6+(7*8*4*5)+3+7+(2+6+5+1+7+6+7*3*(6+2)+6+6)*2+4+2*2+4*9*3)
85
(4+8+4*(8*5*(7*(6*8)+3+(6+(3+7+1*7*5*4)*3)*2*3+5)+6+7*7)*4+2+9*4+7+2*3*(7*6*1*8)+9+9)
97
(9*5+7+8+6+3+9*2+1+7+4+3+9*3*1+4*(4+4*3*1+9*3+(9*5)*1*7*8+2+8+8*7+9*4*9)+(1+1*8+8*9*7+1*4*5*2*5))
89
((3*1*4+6*3+8+4+5+4+2*1+5+3*4)*1+1+(3*2*2+9+5*4*6*9+9+4+1*8+9)*4*8+9+3*7+9*6*9*5+8+3*8+1)
125
(2+(6*5+6+5+3*9+6+2+8*2+2)+6+2*2+2*5*1*2+1*8+1*(4+7*5+8+9+7+3*8*5)+(2+9+5*4*4+1+3*9*6*4*5+(5*(3+4)*9+8+7+9*2)+7+7+2)+8+2+7+5)
113
(8+8*6+3*9*8*7*6*3+5*(7*6*6+3*5+2*4*9*3+5+2+1*4)*1*7+6*8+9+3+2+8*3+8*(2+6*9+2*2*7+8*1*2+9*3+1+5)*(5*8+4*1*2*4*2))
115
(7+9*2+6+5*7+1*7*(9+8+6)*1*2+7+5*9*6*3+4*8*9*6*1*3+7*1+2+5+1*4*9+6*4+7*1*2*4*2+3+((3*4+9+7*1+7+5+3*7*1*7+8*3*8)+7))
99
(9*4+(1+5*7*8+9+1+2)+5+(6*(7+4*5*2+4+8*4+7)+9)*1*3*1+1*2*8+3+(2+9*(1*5*9+7*1+1+7+3*2))+1+3*7*8+9*6)
75
(2*2+((7+8*8*6+(6*6)*7+7*1)*5)*7+3+1*5+1*8*4+(9+6+(7*5+3+1*8*8*9+4+7+9)*3))
117
(8+6*9+2*3+4+2+(6+9+3+7*5*1+2+2+2)*9+4+6*1+6*4+7+7*2+5+2*6*(8*9*8*6+4*2)*5+5*8*3+(6+1+3+3*8*1*2*1+5+6)+1+5+4*7*1*3+1

[Output]
The output file outputs the test case number followin
g the ‘#’ symbol. It is followed by a space, and then
the answer.

#1 672676
#2 1974171
#3 12654
#4 38756
#5 4035
#6 155304
#7 6964
#8 2819
#9 24711
#10 208785

栈实现的代码

#ifndef __Z_STK_H__
#define __Z_STK_H__

#define STK_SZ 1024
typedef struct stack{
   int top;
   int nd[STK_SZ];
}Stack;

int init(Stack *s);
int bempty(Stack *s);
int isfull(Stack *s);
int push(Stack *s,int n);
int pop(Stack *s);
int clear(Stack *s);
int size(Stack *s);
int top(Stack *s);

#endif //Z_STK_H


#include"stdafx.h"
#include <stdio.h>
#include "z_stk.h"

int init(Stack *p)
{
   int i=0;
   if(NULL==p)
      return -1;
   else{
      p->top=0;
      for(i=0;i<STK_SZ;i++)
         p->nd[i]=0;
      return 1;
   }
}

int bempty(Stack *s)
{
   return (0==s->top);
}

int isfull(Stack *s)
{
   return (STK_SZ==s->top);
}

int push(Stack *s,int n)
{
   if(s->top >= STK_SZ)
      return 0;
   s->nd[s->top]=n;
   s->top++;
   return 1;
}

int pop(Stack *s)
{
   int tmp;
   if(s->top==0)
      return 0;
   s->top--;
   tmp=s->nd[s->top];
   s->nd[s->top]=0;
   return tmp;
}

int size(Stack *s)
{
   return s->top;
}

int clear(Stack *s)
{
   s->top=0;
   return 1;
}


int top(Stack *s)
{
   return s->nd[s->top-1];
}

主程序的代码

#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include "z_stk.h"
#define true 1
#define false 0
char ifix[128];
char pfix[128];

int boperator(char ch)
{
    int i;
   char ops[] = "+-*/";
   for (i = 0; i < sizeof(ops) / sizeof(char); i++)
   {
       if (ch == ops[i])
           return true;
   }
   return false;
}

///////////////////////////
// 比较两个操作符的优先级
int precedence(char op1, char op2)
{
   if (op1 == '(')
   {
      return -1;
   }

   if (op1 == '+' || op1 == '-')
   {
      if (op2 == '*' || op2 == '/')
      {
         return -1;
      }
      else
      {
         return 0;
      }
   }

   if (op1 == '*' || op1 == '/')
   {
      if (op2 == '+' || op2 == '-')
      {
         return 1;
      }
      else
      {
         return 0;
      }
   }
   return -1;
}

///////////////////////////////
// 中缀表达式转换成后缀表达式
void ifix2pfix()
{
   int j = 0, len, i;
   char c;
   Stack st;
   init(&st);
   len = strlen(ifix);

   for (i = 0; i < len; i++)
   {
      c = ifix[i];

      if (c == '(')//左括号入栈
          push(&st,c);
      else if (c == ')')//如果是右括号输出到左括号之间的所有字符,左括号不输出
      {
         while (top(&st) != '(')
         {
            pfix[j++] = top(&st);//输出到逆波兰式
            pop(&st);
         }
         pop(&st);//弹出左括号,不输出
      }
      else
      {
         if (!boperator(c))//如果不是运算符直接添加到逆波兰式
             pfix[j++]=c;
         else//运算符
         {
            /* 这两种写法都可以, 这种看着清晰一些, 下面的那种看着简练一些
            if(bempty(&st)==true)
               push(&st,c);
            else{
               while(precedence(top(&st),c) >= 0){
                  pfix[j++]=top(&st);
                  pop(&st);
               }
               push(&st,c);
            }
            */
            while (bempty(&st) == false && precedence(top(&st), c) >= 0)
            {
                 pfix[j++] = top(&st);
                 pop(&st);
            }
            push(&st,c);
         }
      }
   }

   while (bempty(&st) == false)
   {
      pfix[j++] = top(&st);
      pop(&st);
   }
   pfix[j] = 0;
}

////////////////////////
// 后缀表达式求值程序
double pfix_eval(void)
{
    int i;
   Stack st;
   init(&st);
   int len = strlen(pfix);
   char c;

   for (i = 0; i < len; i++)
   {
      c = pfix[i];
      if (boperator(c) == false)
      {
         push(&st, c - '0');
      }
      else
      {
         int op1, op2;
         int val;

         op1 = top(&st);
         pop(&st);
         op2 = top(&st);
         pop(&st);

         switch (c)
         {
         case '+':
            val = op1 + op2;
            break;
         case '-':
            val = op2 - op1;
            break;
         case '*':
            val = op1 * op2;
            break;
         case '/':
            val = op2 / op1;
            break;
         }
         push(&st,val);
      }
   }

   return top(&st);
}

int _tmain(int argc, _TCHAR* argv[])
{
   int tc,T;
   int len;
   double val;
   freopen("01calculator.txt","r",stdin);
   scanf("%d",&T);
   for(tc=1;tc<=T;tc++)
   {
      scanf("%d\n",&len);
      memset(ifix,0,128);
      memset(pfix,0,128);
      gets_s(ifix,len+1);
      if (strlen(ifix) == 0)
          continue;

      ifix2pfix();
      val = pfix_eval();
      printf("#%d %.0f\n",tc, val);
   }

   return 0;
}

2017-06-16 上午调试通过。