中綴表達式轉換為后綴表達式
在表達式計算中，第一要做的就是講中綴表達式轉換成后綴表達式
所采用的方式是，掃描中綴表達式，檢測每個中綴表達式的元素
如果是操作數，則將其加入到輸出的后綴表達式中
如果是操作符，需要對其分析，設定一個操作符棧，
·如果一開始操作符棧為空，則將該操作符壓棧
·這里涉及左括號的兩個優先級，即棧外優先級和棧內優先級，如果左括號在棧外，則其優先級最高，直接將其壓入到操作符棧中，如果左括號在棧內，則其優先級很低，只有在碰到右括號的時候才會彈棧，遇到其他運算符時，直接當其他運算符壓棧。
·這里涉及操作符優先級問題，+ - * / % 這里的優先級相對于壓操作符棧的優先級。即檢測當前操作符與棧頂的操作符優先級，如果當前操作符優先級高于棧頂操作符優先級，需要將當前操作符壓棧，如果當前操作符優先級小于或等于棧頂操作符優先級，則將棧頂操作符出棧，然后再次檢測下一個棧頂操作符的優先級與當前操作符優先級關系。
·對于有左括號和右括號的情況，需要對其做特殊分析。左括號會被壓入棧中，右括號不會。如果當前元素時左括號，由于其棧外優先級最高，可以直接將其壓入棧中，如果棧頂優先級是左括號，并且當前操作符是一般操作符，則直接將當前操作符壓入棧中，如果當前操作符是右括號，則直接將棧頂的左括號出棧。
·中綴表達式和后綴表達式的不同是操作符的相對位置存在變化，當然后綴表達式不會出現括號，也就是后綴表達式中隱式包含了操作符的優先級。另外中綴和后綴表達式中的操作數相對順序是一致的，在轉換的過程中，當當前中綴表達式中的元素時操作數時，直接將其添加到輸出后綴表達式中就可以。
這里利用的棧是操作符棧
在計算后綴表達式的過程中，利用的棧是操作數棧
從中綴表達式轉換為后綴表達式也是一遍掃描中綴表達式即可，當然中間涉及對操作符棧的操作。
修正：( ( 1 + 2 ) * 3 + ( 1 + 10 ) ) / 2 ， ( ( ( 1 + 2 + 3 ) ) ) 的情形。要時刻考慮到括號的特殊性，左括號的棧內優先級和棧外優先級的區別。對于左括號和右括號的主動入棧和出棧以及其他操作符的相對于其入棧和出棧決策要考慮清楚。
實現：
1 #include <iostream>
2 #include <string>
3 #include <vector>
4 #include <stack>
5 #include <map>
6 using namespace std;
7
8 map<string, int> operatorPriors;
9
10 void getInfix(vector<string>& infix)
11 {
12 infix.clear();
13 string tmp;
14 while (cin >> tmp)
15 {
16 infix.push_back(tmp);
17 }
18 }
19
20 void init()
21 {
22 operatorPriors["+"] = 10;
23 operatorPriors["-"] = 10;
24 operatorPriors["*"] = 20;
25 operatorPriors["/"] = 20;
26 operatorPriors["%"] = 20;
27 operatorPriors["("] = 30;
28 operatorPriors[")"] = 0;
29 }
30
31 bool prior(const string& op1, const string& op2)
32 {
33 return operatorPriors[op1] > operatorPriors[op2];
34 }
35
36 bool isOperator(const string& s)
37 {
38 return operatorPriors.find(s) != operatorPriors.end();
39 }
40
41 void print(stack<string> operators)
42 {
43 while (!operators.empty())
44 {
45 cout << operators.top() << ' ';
46 operators.pop();
47 }
48 cout << endl;
49 }
50
51 const vector<string>& infixToPostfix(vector<string>& postfix, const vector<string>& infix)
52 {
53 postfix.clear();
54 stack<string> operators;
55 for (vector<string>::size_type i = 0; i != infix.size(); ++i)
56 {
57 if (isOperator(infix[i]))
58 {
59 if (operators.empty())
60 {
61 operators.push(infix[i]);
62 }
63 else if (operators.top() == "(" && infix[i] != ")" || prior(infix[i], operators.top()))
64 {
65 operators.push(infix[i]);
66 }
67 else
68 {
69 if (infix[i] == ")")
70 {
71 while (operators.top() != "(")
72 {
73 postfix.push_back(operators.top());
74 operators.pop();
75 }
76 operators.pop();
77 }
78 else
79 {
80 postfix.push_back(operators.top());
81 operators.pop();
82 while (!operators.empty() && !prior(infix[i], operators.top()) && operators.top() != "(")
83 {
84 postfix.push_back(operators.top());
85 operators.pop();
86 }
87
88 operators.push(infix[i]);
89 }
90 }
91 }
92 else
93 {
94 postfix.push_back(infix[i]);
95 }
96 }
97 while (!operators.empty())
98 {
99 postfix.push_back(operators.top());
100 operators.pop();
101 }
102 return postfix;
103 }
104
105 int main()
106 {
107 init();
108 vector<string> infix;
109 vector<string> postfix;
110 getInfix(infix);
111 infixToPostfix(postfix, infix);
112 for (vector<string>::size_type i = 0; i != postfix.size(); ++i)
113 {
114 cout << postfix[i] << ' ';
115 }
116 cout << endl;
117 return 0;
118 }
posted @
2011-06-29 01:07 unixfy 閱讀(580) |
評論 (0) |
編輯 收藏后綴表達式的計算
表達式運算過程中，需要先做中綴表達式到后綴表達式的轉換。
這里現對后綴表達式求值進行解答。
對后綴表達式進行掃描，遇到操作數將操作數壓棧，遇到運算符將操作數出棧，進行運算，將運算的結果壓入到操作數棧中。
注意，對于雙目運算符，在堆操作數棧出棧的時候要注意，后彈出的操作符為左邊的操作符，不要弄反了。
之前的做法是錯誤的，把后綴表達式存在一個棧中，只對棧頂操作，對于 a b c + * 這種情況不成立。
實現如下：
1 #include <iostream>
2 #include <vector>
3 #include <string>
4 #include <stack>
5 #include <sstream>
6 #include <cstdlib>
7 using namespace std;
8
9 void getPost(vector<string>& post)
10 {
11 post.clear();
12 string tmp;
13 while (cin >> tmp)
14 {
15 post.push_back(tmp);
16 }
17 }
18
19 double stringToDouble(const string& s)
20 {
21 return (atof(s.c_str()));
22 }
23
24 double evalPost(const vector<string>& post)
25 {
26 stack<double> operands;
27 int a, b;
28 for (vector<string>::size_type i = 0; i != post.size(); ++i)
29 {
30 if (post[i] == "+")
31 {
32 b = operands.top();
33 operands.pop();
34 a = operands.top();
35 operands.pop();
36 operands.push(a + b);
37 }
38 else if (post[i] == "-")
39 {
40 b = operands.top();
41 operands.pop();
42 a = operands.top();
43 operands.pop();
44 operands.push(a - b);
45 }
46 else if (post[i] == "*")
47 {
48 b = operands.top();
49 operands.pop();
50 a = operands.top();
51 operands.pop();
52 operands.push(a * b);
53 }
54 else if (post[i] == "/")
55 {
56 b = operands.top();
57 operands.pop();
58 a = operands.top();
59 operands.pop();
60 operands.push(a / b);
61 }
62 else if (post[i] == "%")
63 {
64 b = operands.top();
65 operands.pop();
66 a =operands.top();
67 operands.pop();
68 operands.push(a - b);
69 }
70 else
71 {
72 // stringstream ss;
73 // ss << post[i];
74 // ss >> a;
75 operands.push(stringToDouble(post[i]));
76 }
77 }
78 return operands.top();
79 }
80
81 int main()
82 {
83 vector<string> post;
84 getPost(post);
85 cout << evalPost(post) << endl;
86 return 0;
87 }
posted @
2011-06-28 23:20 unixfy 閱讀(696) |
評論 (0) |
編輯 收藏繼承層次中的輸入輸出運算符重載
class A
{
};
class B : public A
{
};
方案一
可對 A 進行重載輸入輸出運算符，然后也對 B 重載相應版本的輸入輸出運算符
方案二
只對 A 進行重載輸入輸出運算符，對 A 定義一個 virtual print 函數，在 B 中也對該 virtual 函數 override
在重載的輸入輸出運算符中調用 virtual print 函數
1 #include <iostream>
2 #include <string>
3 using namespace std;
4
5 class Complex
6 {
7 protected:
8 // private:
9 int nR;
10 int nI;
11 public:
12 Complex(int tmpR = -100, int tmpI = -100);
13 virtual void display();
14 virtual ostream& print(ostream& os) const;
15 friend ostream& operator << (ostream&, const Complex&);
16 };
17
18 class NameComplex : public Complex
19 {
20 private:
21 string strName;
22 public:
23 NameComplex(const string& = "abc", int = -100, int = -100);
24 virtual void display();
25 virtual ostream& print(ostream& os) const;
26 // friend ostream& operator << (ostream&, const NameComplex&);
27 };
28
29 Complex::Complex(int tmpR, int tmpI) : nR(tmpR), nI(tmpI) {}
30
31 void Complex::display()
32 {
33 cout << nR << endl;
34 cout << nI << endl;
35 }
36
37 ostream& Complex::print(ostream& os) const
38 {
39 os << nR << ' ' << nI;
40 return os;
41 }
42
43 /*
44 ostream& operator << (ostream& os, const Complex& rhs)
45 {
46 os << rhs.nR << ' ' << rhs.nI;
47 return os;
48 }
49 */
50
51 ostream& operator << (ostream& os, const Complex& rhs)
52 {
53 return rhs.print(os);
54 }
55
56 NameComplex::NameComplex(const string& str, int nR, int nI) : Complex(nR, nI), strName(str) {}
57
58 void NameComplex::display()
59 {
60 cout << strName << endl;
61 Complex::display();
62 }
63
64 /*
65 ostream& operator << (ostream& os, const NameComplex& rhs)
66 {
67 os << rhs.strName << ' ';
68 operator << (os, static_cast<Complex>(rhs));
69 return os;
70 }
71 */
72
73 ostream& NameComplex::print(ostream& os) const
74 {
75 os << strName << ' ';
76 return Complex::print(os);
77 }
78
79 int main()
80 {
81 Complex a;
82 cout << a << endl;
83
84 NameComplex b;
85 cout << b << endl;
86 }
http://topic.csdn.net/u/20110627/22/c4c0b809-13f4-482d-aa26-5faf5c1fc0f0.html?54375
posted @
2011-06-27 23:44 unixfy 閱讀(249) |
評論 (0) |
編輯 收藏還是利用字符 ASCII 定義一個表，即
static char x[256];
memset(x, 0, sizeof (x));
這樣一遍掃描即可，在掃描的過程中，首先檢測當前字符是否出現，如果沒出現，將對應 x 的元素置為出現狀態，并且將該字符加入到輸出字符串中，如果已經出現過，則忽略
實現如下：
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 void changestr(const char* pIn, char* pOut)
6 {
7 static char x[256];
8 int i = 0, j = 0;
9 memset(x, 0, sizeof (x));
10 for (i = 0, j = 0; i < strlen(pIn); ++i)
11 {
12 if (x[pIn[i]] == 0)
13 {
14 x[pIn[i]] = 1;
15 pOut[j] = pIn[i];
16 ++j;
17 }
18 }
19 pOut[j] = '\0';
20 }
21
22 int main()
23 {
24 char pIn[100], pOut[100];
25 while (scanf("%s", pIn) != EOF)
26 {
27 changestr(pIn, pOut);
28 printf("%s\n", pOut);
29 }
30 return 0;
31 }
posted @
2011-06-27 22:45 unixfy 閱讀(553) |
評論 (0) |
編輯 收藏一個字符串由 a - z 26 個字符組成，其中只有一個字符出現的次數為奇數次，其他 25 個字符出現次數都是偶數次。
找出這個出現奇數次的字符。
這個問題，最直觀的解法就是遍歷一下，記錄每個字符的出現次數 int x[26] = {0};
然后掃描 x 檢測即可。
但是回過頭來想一下這樣做有必要嗎，看看我們這樣做的后果是什么，我們得到了所有字符出現的次數，然后檢測以得到出現次數為奇數的字符，這種方法是可以的，但是沒有必要得到每個字符的出現次數，也就是說我們得到了大量的冗余信息，這種冗余信息是需要代價的。這也就導致了我們的這種方法效率不高。
把問題認識清楚很重要，最重要。我們只需要找到出現次數為奇數的字符，不需要得到每個字符的具體出現次數。我們可以利用位運算中的異或。
異或的運算性質是：
a ^ a = 0
a ^ a ^ a = a
偶數個本身異或運算為 0
奇數個本身異或運算為其本身
也就是說，我們可以對字符串中的每個字符，一遍掃描，做異或運算，由于 25 個字符出現偶數次，1 個字符出現奇數次，一遍掃描異或運算得到的結果即是出現次數為奇數的那個字符。
總結：
一個問題的解決，要從認清問題開始。求解問題的好的方法是觀察我們的解決過程，看看是不是中間得到了冗余的信息，如果存在這種冗余信息，說明我們的解法做了不必要的計算，有更大的改進空間。
異或運算很巧妙。關于它的巧妙運用很多地方都有提到。其中《編程之美》中有關于異或運算的運用。
posted @
2011-06-27 18:49 unixfy 閱讀(259) |
評論 (0) |
編輯 收藏找出字符串中最大的子串
子串：當重復出現某個字符時，這個字符串就是子串
例如：
字符串 abcd13agbf
子串為：abcd13a, bcd13agb
求解 1
兩重遍歷字符串，檢測左右兩個端點的字符是否一樣，如果相等，則是子串
這種方法直觀，時間復雜度為 O(N ^ 2)。
求解 2
盡可能從問題中挖掘潛在的信息，獲得的信息越多越有利于解決問題，也就越有可能獲得高效的解法。
針對字符，我們知道其 ASCII 范圍是 0 - 255 ，我們這設計一個二維數組
int x[256][100];
x 存儲每個字符所在的位置
用 int n[256]; 記錄每個字符出現的次數
掃描一遍字符串，即可得到我們想要的信息并存儲于 x 和 n 中
然后對 x 進行掃描，即可得到最大的子串
第一次掃描字符串時間復雜度是 O(N)
第二次掃描 x ，時間復雜度也是 O(N)
總的時間復雜度為 O(N)
實現：
1 #include <iostream>
2 using namespace std;
3
4 char* maxSubStr(char* s, const char* str)
5 {
6 int left = 0, right = 0;
7 int max = 0;
8 for (int i = 0; i < strlen(str); ++i)
9 {
10 int temp = 1;
11 for (int j = i + 1; j < strlen(str); ++j)
12 {
13 if (str[i] == str[j])
14 {
15 ++temp;
16 if (temp > max)
17 {
18 max = temp;
19 left = i;
20 right = j;
21 }
22 }
23 else
24 {
25 ++temp;
26 }
27 }
28 }
29 int j = 0;
30 for (int i = left; i <= right; ++i, ++j)
31 {
32 s[j] = str[i];
33 }
34 s[j] = '\0';
35 return s;
36 }
37
38 char* maxSubStrX(char* s, const char* str)
39 {
40 static int x[256][100];
41 static int n[256];
42 memset(x, -1, sizeof (x));
43 memset(n, 0, sizeof (n));
44 for (int i = 0; i < strlen(str); ++i)
45 {
46 x[ str[i] ][ n[ str[i] ] ] = i;
47 ++n[str[i]];
48 }
49 int left = 0, right = 0;
50 int max = 0;
51 for (int i = 0; i < 256; ++i)
52 {
53 for (int j = 0; j < n[i] - 1; ++i)
54 {
55 if (x[i][j + 1] - x[i][j] > max)
56 {
57 max = x[i][j + 1] - x[i][j];
58 left = x[i][j];
59 right = x[i][j + 1];
60 }
61 }
62 }
63 int j = 0;
64 for (int i = left; i <= right; ++i, ++j)
65 {
66 s[j] = str[i];
67 }
68 s[j] = '\0';
69 return s;
70 }
71
72 int main()
73 {
74 char str[100], s[100];
75 while (cin >> str)
76 {
77 cout << maxSubStr(s, str) << endl;
78 cout << maxSubStrX(s, str) << endl;
79 }
80 return 0;
81 }
posted @
2011-06-27 18:29 unixfy 閱讀(644) |
評論 (0) |
編輯 收藏利用棧存儲中綴表達式的各個元素
例如：
1 2 + 3 *
3 3 *
9
1 // 后綴表達式求解結果
2
3 #include <iostream>
4 #include <stack>
5 #include <string>
6 #include <sstream>
7 #include <algorithm>
8 using namespace std;
9
10 void printPost(const stack<string>& post)
11 {
12 stack<string> temp(post);
13 while (!temp.empty())
14 {
15 cout << temp.top() << ' ';
16 temp.pop();
17 }
18 cout << endl;
19 }
20
21 void clearPost(stack<string>& post)
22 {
23 while (!post.empty())
24 {
25 post.pop();
26 }
27 }
28
29 void getPost(stack<string>& post)
30 {
31 clearPost(post);
32 string t;
33 stack<string> temp;
34 while (cin >> t)
35 {
36 temp.push(t);
37 }
38 while (!temp.empty())
39 {
40 post.push(temp.top());
41 temp.pop();
42 }
43 }
44
45 double computePost(const stack<string>& rhs)
46 {
47 stack<string> post(rhs);
48 double d1, d2;
49 double dd;
50 string optor;
51 string temp;
52 while (post.size() >= 3)
53 {
54 d1 = atof(post.top().c_str());
55 post.pop();
56 d2 = atof(post.top().c_str());
57 post.pop();
58 optor = post.top();
59 post.pop();
60 switch (optor[0])
61 {
62 case '+':
63 dd = d1 + d2;
64 break;
65 case '-':
66 dd = d1 - d2;
67 break;
68 case '*':
69 dd = d1 * d2;
70 break;
71 case '/':
72 dd = d1 / d2;
73 break;
74 default:
75 break;
76 }
77 if (post.empty())
78 {
79 break;
80 }
81 stringstream ss;
82 ss << dd;
83 ss >> temp;
84 post.push(temp);
85 printPost(post);
86 }
87 return dd;
88 }
89
90 int main()
91 {
92 stack<string> post;
93 cout << "Input:" << endl;
94 getPost(post);
95 printPost(post);
96 cout << computePost(post) << endl;
97 return 0;
98 }
posted @
2011-06-25 19:10 unixfy 閱讀(422) |
評論 (0) |
編輯 收藏字符轉換函數的實現
第一種方法，利用 ASCII 碼大小計算
1 char mytoupper(char c)
2 {
3 if (c >= 'a' && c <= 'z')
4 {
5 c += ('A' - 'a');
6 }
7 return c;
8 }
9
10 char mytolower(char c)
11 {
12 if (c >= 'A' && c <= 'Z')
13 {
14 c += ('a' - 'A');
15 }
16 return c;
17 }
第二種方法，利用位運算
'a' - 'z': 97 - 122
'A' - 'Z': 65 - 90
'a' 與 'A' 正好相差 32 ，即 20x ，0010 0000
大寫字母的范圍是 0100 0001 - 0101 1010
小些字母的范圍是 0110 0001 - 0111 1010
對于大寫字母第 5 位都為 0
對于小些字母第 5 為都為 1
可以利用位運算的方法，即對大寫字母的第 5 位進行操作，但要保持其他位不變
即利用 MASK = 0010 0000
大寫 -> 小寫
'a' = 'A' | (0010 0000);
小寫 -> 大寫
'A' = 'a' & (1101 1111);
這樣做也不需要檢測，如果本來就是小寫，在做 或 操作時，第 5 位不變，維持 1
如果本來就是大寫，在做 與操作時，第 5 位還是不變，維持 0
1 char mytoupper(char c)
2 {
3 return c & (0xDF);
4 }
5
6 char mytolower(char c)
7 {
8 return c | (0x20);
9 }
http://m.shnenglu.com/qinqing1984/archive/2011/06/25/149427.html
posted @
2011-06-25 18:24 unixfy 閱讀(113) |
評論 (0) |
編輯 收藏一個算法的博客
幾個算法題目
1.
實現過程中參考了網上別人的博客，主要思想是利用一個輔助棧記錄 min 的索引。
1 #include <iostream>
2 #include <ctime>
3 #include <cassert>
4 using namespace std;
5
6 class MinStack
7 {
8 private:
9 int stack[100];
10 int p;
11 int minstack[100];
12 int q;
13 public:
14 MinStack() : p(0), q(0) {}
15 bool empty()
16 {
17 return p == 0;
18 }
19 bool minEmpty()
20 {
21 return q == 0;
22 }
23 void push(int i)
24 {
25 stack[p++] = i;
26 if (minEmpty())
27 {
28 minstack[q++] = p - 1;
29 }
30 else
31 {
32 if (i <= stack[minTop()])
33 {
34 minstack[q++] = p - 1;
35 }
36 }
37 }
38 void pop()
39 {
40 assert(!empty());
41 if (top() == stack[minTop()])
42 {
43 minPop();
44 }
45 --p;
46 }
47 int min()
48 {
49 assert(!empty());
50 return stack[minTop()];
51 }
52 void minPop()
53 {
54 assert(!minEmpty());
55 --q;
56 }
57 int top()
58 {
59 assert(!empty());
60 return stack[p - 1];
61 }
62 int minTop()
63 {
64 assert(!minEmpty());
65 return minstack[q - 1];
66 }
67 };
68
69 int main()
70 {
71 MinStack ms;
72 srand(time(0));
73 for (int i = 0; i < 10; ++i)
74 {
75 int n = rand() % 100;
76 ms.push(n);
77 }
78 while (!ms.empty())
79 {
80 cout << ms.top() << '\t' << ms.min() << endl;
81 ms.pop();
82 }
83 return 0;
84 }
2.
1 /*
2 *
3 *先統計所有查詢的次數，所有查詢有 300 萬個，255 * 300 * 10000B = 765 MB，可以存入內存。這里使用 STL 中的 map。所得時間復雜度為 O(NlogM)，N 為所有的查詢，包括重復的，M 為不重復的查詢。更好的方法是用散列。
4 *
5 *然后遍歷 map，維護一個大小為 10 的集合，在遍歷 map 時，比較當前查詢的出現次數與集合中出現次數最小的查詢的出現此時比較，如果大于，將當前查詢替換到集合中。
6 *這里的集合還是用的 map，時間復雜度為 O（MlogK），這里 K = 10。
7 *
8 */
9
10 #include <iostream>
11 #include <fstream>
12 #include <map>
13 #include <string>
14 using namespace std;
15
16 void statistics(map<string, int>& data, const string& query)
17 {
18 ++data[query];
19 }
20
21 void findTopK(multimap<int, string>& topK, int k, const map<string, int>& data)
22 {
23 topK.clear();
24 for (map<string, int>::const_iterator cit = data.begin(); cit != data.end(); ++cit)
25 {
26 if (topK.size() < k)
27 {
28 topK.insert(make_pair(cit->second, cit->first));
29 }
30 else
31 {
32 if (cit->second > topK.begin()->first)
33 {
34 topK.erase(topK.begin());
35 topK.insert(make_pair(cit->second, cit->first));
36 }
37 }
38 }
39 }
40
41 int main()
42 {
43 ifstream fin("queryfile.txt");
44 map<string, int> data;
45 multimap<int, string> top10;
46 string query;
47 while (getline(fin, query))
48 {
49 statistics(data, query);
50 }
51 findTopK(top10, 10, data);
52 for (multimap<int, string>::const_reverse_iterator cit = top10.rbegin(); cit != top10.rend(); ++cit)
53 {
54 cout << cit->second << '\t' << cit->first << endl;
55 }
56
57 return 0;
58 }
3.
1 #include <iostream>
2 #include <string>
3 using namespace std;
4
5 char solve(const string& s)
6 {
7 static int times[26] = {0};
8 memset(times, 0, sizeof (times));
9 for (size_t i = 0; i < s.size(); ++i)
10 {
11 ++times[s[i] - 'a'];
12 }
13 for (size_t i = 0; i < s.size(); ++i)
14 {
15 if (times[s[i] - 'a'] == 1)
16 {
17 return s[i];
18 }
19 }
20 return 0;
21 }
22
23 int main()
24 {
25 string s = "abaccdeff";
26 cout << solve(s) << endl;
27 return 0;
28 }
posted @
2011-06-25 16:44 unixfy 閱讀(99) |
評論 (0) |
編輯 收藏
除以 1000 ， 對余數進行處理
1 #include <iostream>
2 using namespace std;
3
4 char* reverse(char* s, int low, int high)
5 {
6 while (low < high)
7 {
8 s[low] ^= s[high];
9 s[high] ^= s[low];
10 s[low] ^= s[high];
11 ++low;
12 --high;
13 }
14 return s;
15 }
16
17 char* format_thousands_separator(char a[], unsigned long val)
18 {
19 char* ret = a;
20 char temp[4];
21 int t;
22 int n = 0;
23 while (val > 1000)
24 {
25 t = val % 1000;
26 if (t >= 100)
27 {
28 itoa(t, temp, 10);
29 reverse(temp, 0, 2);
30 //cout << temp << endl;
31 strcat(ret, temp);
32 //cout<< "test" << ret << endl;
33 }
34 else if (t >= 10)
35 {
36 itoa(t, temp, 10);
37 reverse(temp, 0, 1);
38 strcat(ret, temp);
39 strcat(ret, "0");
40 }
41 else
42 {
43 itoa(t, temp, 10);
44 strcat(ret, temp);
45 strcat(ret, "00");
46 }
47 strcat(ret, ",");
48 n += 4;
49 val /= 1000;
50 ret[n] = '\0';
51 cout << ret << endl;
52 }
53 if (val >= 100)
54 {
55 itoa(val, temp, 10);
56 reverse(temp, 0, 2);
57 strcat(ret, temp);
58 n += 3;
59 }
60 else if (val >= 10)
61 {
62 itoa(val, temp, 10);
63 reverse(temp, 0, 1);
64 strcat(ret, temp);
65 n += 2;
66 }
67 else
68 {
69 itoa(val, temp, 10);
70 strcat(ret, temp);
71 ++n;
72 }
73 reverse(ret, 0, n - 1);
74 ret[n] = '\0';
75 return ret;
76 };
77
78 int main()
79 {
80 unsigned long ul;
81 char sul[20] = {0};
82 while (cin >> ul)
83 {
84 cout << format_thousands_separator(sul, ul) << endl;
85 }
86 return 0;
87 }
先轉換成一個 字符串 ，然后從右掃描，加逗號，然后反轉
1 #include <iostream>
2 #include <sstream>
3 #include <string>
4 #include <algorithm>
5 using namespace std;
6
7 const string& format_thousands_separator(string& s, unsigned long val)
8 {
9 s.clear();
10 char t[20];
11 string temp(ltoa(val, t, 10));
12
13 int n = 0;
14 for (string::const_reverse_iterator cit = temp.rbegin(); cit != temp.rend(); ++cit)
15 {
16 ++n;
17 s += *cit;
18 if (n == 3)
19 {
20 s += ',';
21 n = 0;
22 }
23 }
24 reverse(s.begin(), s.end());
25 return s;
26 }
27
28 int main()
29 {
30 unsigned long ul;
31 string sul;
32 while (cin >> ul)
33 {
34 cout << format_thousands_separator(sul, ul) << endl;
35 }
36 return 0;
37 }
http://m.shnenglu.com/qinqing1984/archive/2011/06/24/149366.html
posted @
2011-06-24 16:46 unixfy 閱讀(484) |
評論 (0) |
編輯 收藏