2011 1001 (中序轉後序 )

// Test.cpp : 定義主控台應用程式的進入點。
//
#include "stdafx.h" // 不要管
#include<iostream>
#include<sstream>
using namespace std;
//宣告一個資料型態叫做Stack
class StackChar{
private:
int top; //紀錄目前index位置
public:
char stack[1000]; //放資料的地方
StackChar()
{
top = -1; // 沒有東西
};
void push(char input)
{
stack[++top] = input;
};
char pop()
{
return stack[top--];
};
char peak()
{
return stack[top];
};
bool IsEmpty()
{
return (top <= -1)? true : false;
}
};
//宣告一個資料型態叫做Stack
class StackInteger{
private:
int top; //紀錄目前index位置
public:
int stack[1000]; //放資料的地方
StackInteger()
{
top = -1; // 沒有東西
};
void push(int input)
{
stack[++top] = input;
};
int pop()
{
return stack[top--];
};
int peak()
{
return stack[top];
};
bool IsEmpty()
{
return (top <= -1)? true : false;
}
};
int order(char op); // 取得算數優先權 */ > +-
string infixToPostfix(string infix); // 中序轉後序
int pofixComput(string pofix);
int _tmain(int argc, _TCHAR* argv[]) //int main()
{
string input;
getline(cin, input);
//string postfix = infixToPostfix(input);
cout << endl << pofixComput(
infixToPostfix(input)
);
string str;
getline(cin, str);
return 0;
}
// 取得算數優先權 */ > +-
int order(char op)
{
int returnValue = 0;
switch(op)
{
case '*' :
case '/' :
returnValue = 2;
break;
case '+':
case '-':
returnValue = 1;
break;
default:
returnValue = 0;
break;
}
return returnValue;
}
// 中序轉後序
string infixToPostfix(string infix)
{
istringstream issstream(infix); //輸入
ostringstream postfix; //輸出
string word; // 暫時儲存 temp
StackChar stack;
while(issstream >> word)
{
if( isdigit(word[0]))
{
postfix << word << " ";
}
else
{
switch(word[0])
{
case '(':
stack.push('(');
break;
case ')':
while(stack.peak() != '(' )
{
postfix << stack.pop() << " ";
}
stack.pop();
break;
case '+': case '-': case '*': case '/':
if( stack.IsEmpty()) //如果Stack沒資料
{
stack.push(word[0]);
}
else //如果Stack至少有一個資料
{
if( order(word[0] ) > order( stack.peak() ) )
{
stack.push(word[0]);
}
else
{
do{
postfix << stack.pop() << " ";
}while //如果還有資料且優先權小於等於目前的word[0]，繼續pop()
( !stack.IsEmpty() &&
order(word[0]) <= order( stack.peak() )
);
stack.push(word[0]);
}
}
break;
default:
break;
}
}
}
//清空stack
if(stack.IsEmpty() ) //如果沒資料
{
;
}
else
{
do{
postfix << stack.pop() << " ";
}while( !stack.IsEmpty() );
}
return postfix.str();
}
// 後序計算
int pofixComput(string pofix)
{
istringstream issstream(pofix); //輸入
string word;
StackInteger stackInt;
int i , j ;
while( issstream >>word )
{
if(isdigit(word[0])) //如果是數字
{
stackInt.push(
atoi(word.c_str())
);
}
else // 如果不是數字
{
i = stackInt.pop();
j = stackInt.pop();
switch(word[0])
{
case '+':
stackInt.push(j + i);
break;
case '-':
stackInt.push(j - i);
break;
case '*':
stackInt.push(j * i);
break;
case '/':
stackInt.push(j / i);
break;
default:
break;
}
}
} // End While
return stackInt.pop();
}

複製代碼

Mai 買大誠 [E-Mail : mainword@dlinfo.tw, mainword@gmail.com] 手機 : 0911-116194
Sun Certified Java Programmer

DL Info 鼎侖資訊 [886-7-969-0998] 高雄市苓雅區光華一路206號6樓之2

返回列表

2011 1001 (中序轉後序 )

[收藏此主題] [關注此主題的新回復]

[通過 QQ、MSN 分享給朋友]