/*
Program: evalExpression-v2.c (Report comments/bugs to chikh@yuntech.edu.tw)
Function: 整合書範例infixTopostfix.c程式與第三章末習題第四題的要求，使得程式可接受使用者
		從鍵盤輸入中序表示式字串，隨即顯示對應的後序表示式，再依此進行運算並顯示結果值。 
		與evalExpression-v1.c功能相同，唯一差異在evaluate()函數的實作方式；此版以strtok()
		作字串剖析，以空白作分隔字元，分離出所需的運算元與運算子。 
Notes:
	10+20*(50-30)/2^4-6*8
	10+20*(-50+30)/-2^4-6*8
	10.5+20.8*(50.1-30.6)/2.5^4-6.6*8.2
	10.5+20.8*(-50.1+30.6)/2.5^-4-6.6*8.2
	10-30*(+50-20)/-2^-4+7.5*-6
	10+30*(+50.2+3.8)/+2^2.5+15*-6.5 
*/

#include <stdio.h>
#include <string.h>	/* for strtok() */
#include <math.h>	/* for pow() */
#include <ctype.h>	/* for isdigit() */

#define MAX 120

void infix_to_postfix(char [], int, char []);  /* 由中序轉後序函數 */
int compare(char, char);	/* 比較兩個運算子函數 */
float evaluate(char []);	/* 新訂的函數，為後序式實作所需的數學運算並回傳結果值 */ 

/* 在中序表示法佇列及暫存堆疊中，運算子的優先順序表，其優先值為INDEX/2 */
char infix_priority[9] = {'#', ')', '+', '-', '*', '/', '^', '('};
char stack_priority[8] = {'#', '(', '+', '-', '*', '/', '^'};

int main()
{
    int i, index = -1;
    char infix_q[MAX], postExpr[2*MAX] = {0};  /* 儲存使用者輸入中序式字元串，轉換為後序式字串存於postExpr */ 
    
	printf("\n請輸入中序表示式(支援+-*/^()運算) => ");
    
	while (infix_q[index] != '\n')
        infix_q[++index] = getchar();
    infix_q[index] = '#';  /* 原輸入的最後一個字元取代為'#'，作為運算式字串結尾 */
    
    printf("\n對應的後序表示式：");
    infix_to_postfix(infix_q,index,postExpr);
	//printf("\n --> %s\n",postExpr);
	printf("\n\n運算結果=%g",evaluate(postExpr));
	//printf("\t(正確值=%g)\n\n",10+20*(50-30)/pow(2,4)-6*8);
	//printf("\t(正確值=%g)\n\n",10+20*(-50+30)/pow(-2,4)-6*8);
	printf("\t(正確值=%g)\n\n",10.5+20.8*(50.1-30.6)/pow(2.5,4)-6.6*8.2);
	//printf("\t(正確值=%g)\n\n",10.5+20.8*(-50.1+30.6)/pow(2.5,-4)-6.6*8.2);
	//printf("\t(正確值=%g)\n\n",10-30*(+50-20)/pow(-2,-4)+7.5*-6);
	//printf("\t(正確值=%g)\n\n",10+30*(+50.2+3.8)/pow(2,2.5)+15*-6.5);
	
    return 0;
}

void infix_to_postfix(char infix_q[], int index, char postExpr[])
{
    int top = 0, ctr, tag = 1, i = 0;
    char c, stack_t[MAX]; 	/* 儲存還不必輸出的運算子 */
    
	stack_t[top] = '#'; 	/* 於堆疊最底下加入#為結束符號 */
    for (ctr = 0; ctr <= index; ctr++) {	/* 運算式視為字元串，從第0字元開始，逐字掃描，直至最後一個字元為止 */
        switch (infix_q[ctr]) {	/* 檢視ctr索引值對應的字元內容，查看是否吻合底下任一情況 */
            case ')':	/* 輸入為')'，將輸出堆疊內運算子，直到彈出'('為止 */ 
            	printf(" ");	/* 螢幕顯示加入空白間隔 */
				sprintf(postExpr,"%s ",postExpr);
                while (stack_t[top] != '(') {
                	printf("%c ",c=stack_t[top--]);
                	sprintf(postExpr,"%s%c ",postExpr,c);
				}
                top--;	/* 把'('一併移除 */
                break;
            
            case '#':	/* 輸入為#，代表已掃描到最末字元，於是把堆疊內尚未輸出的運算子通通彈出 */
            	printf(" ");
            	sprintf(postExpr,"%s ",postExpr); /* 導入空白於後序式字串 */ 
                while (stack_t[top] != '#') {
                	printf("%c ",c=stack_t[top--]);
                	sprintf(postExpr,"%s%c ",postExpr,c);
				}
                break;
                
            case '(':
            case '^':
            case '*':
            case '/':
            	printf(" ");
            	sprintf(postExpr,"%s ",postExpr);
                while (compare(stack_t[top],infix_q[ctr])) {
                	printf("%c ",c=stack_t[top--]);
                	sprintf(postExpr,"%s%c ",postExpr,c);
				}
                stack_t[++top] = infix_q[ctr];
                tag = 1;
                break;
            case '+':
            case '-':
                if (tag == 1) { /* 判斷 '(' '^' '*' '/' 後的 +- 號是否表示正負的一元運算子 */
                    stack_t[++top] = infix_q[ctr];
                    tag = 2;  
                }
                else {
                	printf(" ");
                	sprintf(postExpr,"%s ",postExpr);
                    while (compare(stack_t[top],infix_q[ctr])) {
                        printf("%c ",c=stack_t[top--]);
                        sprintf(postExpr,"%s%c ",postExpr,c);
					}                        
                    stack_t[++top] = infix_q[ctr];
                    tag = 1;
                }
                break;
            
            case ' ': 
            	break; /* do nothing，直接略過 */ 
            /* 輸入為運算元，則直接輸出 */
            default:
                for (i = 0; isdigit(infix_q[ctr+i]) || infix_q[ctr+i]=='.'; i++) {
                	printf("%c",c=infix_q[ctr+i]);
                	sprintf(postExpr,"%s%c",postExpr,c);
				} 
				ctr += (i-1);
                if (tag == 2) {	/* 將存放在堆疊的負號輸出 */
					printf(" %c ",c=stack_t[top--]); /* 視同彈出堆疊頂端的元素 */  
                    sprintf(postExpr,"%s %c ",postExpr,c=='-'?'_':'@');
            	}
                tag = 0;
                break;
        }
    }
}

/* 比較兩運算子優先權，若輸入運算子小於等於堆疊中運算子，則傳回值為 1，否則為 0 */
int compare(char stack_o, char infix_o)
{
    int index_s = 0, index_i = 0;
    while (stack_priority[index_s] != stack_o)
        index_s++;
    while (infix_priority[index_i] != infix_o)
        index_i++;
    return index_s/2 >= index_i/2 ? 1 : 0;
}

float evaluate(char expr[])
{
	char *token;
	float stack[MAX], a, b, c;
	int top = -1;
   
	token = strtok(expr," ");  /* 取得第一個符記 */ 
	while (token != NULL) { 	/* 若不為空，則嘗試繼續剖析字串 */ 
    	if (atof(token)!=0.0) 
    		stack[++top] = atof(token);
    	else {
    		b = stack[top--];
    		a = stack[top--];
    		switch(token[0]) {
    			case '+':
    				c = a+b;
    				break;
    			case '-':
    				c = a-b;
    				break;
    			case '@':
    				stack[++top] = a; /* 多取出的資料推回堆疊，因為一元運算 */ 
    				c = b;
    				break;
				case '_':
    				stack[++top] = a; /* 多取出的資料推回堆疊，因為一元運算 */
    				c = -b;
    				break;
    			case '*':
    				c = a*b;
    				break;
    			case '/':
    				c = (float)a/b;
    				break;
    			case '^':
    				c = (float)pow(a,b);
    				break;
			}
			stack[++top] = c;
		}
      	token = strtok(NULL," "); /* 很特別的寫法，請同學多加留意 */ 
   	}
   	
   	return stack[top];
}