137 lines
3.2 KiB
C
137 lines
3.2 KiB
C
#include <stdio.h>
|
||
#include <stdlib.h>
|
||
#define MAX 100
|
||
|
||
// 宣告全域變數
|
||
char input[MAX]; // 儲存輸入的算式
|
||
char stack[MAX]; // 用來暫存運算子的堆疊
|
||
int top = -1; // 堆疊的頂端位置
|
||
|
||
// === 堆疊的基本操作 ===
|
||
void push(char c) {
|
||
top++;
|
||
stack[top] = c;
|
||
}
|
||
|
||
char pop() {
|
||
char c = stack[top];
|
||
top--;
|
||
return c;
|
||
}
|
||
|
||
// === 檢查運算子優先順序 ===
|
||
int get_priority(char op) {
|
||
switch(op) {
|
||
case '+':
|
||
case '-':
|
||
return 1;
|
||
case '*':
|
||
case '/':
|
||
return 2;
|
||
case '^':
|
||
return 3;
|
||
case 'n': // 負號的優先順序最高
|
||
return 4;
|
||
default:
|
||
return 0;
|
||
}
|
||
}
|
||
|
||
// === 檢查字元是否為運算子 ===
|
||
int is_operator(char c) {
|
||
return (c == '+' || c == '-' || c == '*' || c == '/' || c == '^');
|
||
}
|
||
|
||
// === 檢查是否為負號 ===
|
||
int is_negative_sign(char *expr, int pos) {
|
||
// 如果是第一個字元，就是負號
|
||
if (pos == 0) return 1;
|
||
|
||
// 檢查前一個非空白字元
|
||
int prev = pos - 1;
|
||
while (prev >= 0 && expr[prev] == ' ') prev--;
|
||
|
||
if (prev < 0) return 1; // 如果前面都是空白，也是負號
|
||
|
||
// 如果前一個字元是運算子或左括號，就是負號
|
||
return (is_operator(expr[prev]) || expr[prev] == '(');
|
||
}
|
||
|
||
// === 主要轉換函式 ===
|
||
void convert_to_postfix() {
|
||
int i = 0;
|
||
|
||
printf("後序表示法：");
|
||
|
||
while(input[i] != '\0') {
|
||
char now = input[i];
|
||
|
||
// 處理數字（包含負數）
|
||
if (now >= '0' && now <= '9') {
|
||
printf("%c", now);
|
||
while(input[i+1] >= '0' && input[i+1] <= '9') {
|
||
i++;
|
||
printf("%c", input[i]);
|
||
}
|
||
printf(" ");
|
||
}
|
||
// 處理負號
|
||
else if (now == '-' && is_negative_sign(input, i)) {
|
||
push('n'); // 使用特殊字元'n'表示負號
|
||
i++;
|
||
// 直接輸出數字部分
|
||
while(input[i] >= '0' && input[i] <= '9') {
|
||
printf("%c", input[i]);
|
||
i++;
|
||
}
|
||
printf(" ");
|
||
// 輸出負號
|
||
printf("-");
|
||
i--; // 回退一個位置，因為while循環還會加一
|
||
}
|
||
// 處理左括號
|
||
else if(now == '(') {
|
||
push(now);
|
||
}
|
||
// 處理右括號
|
||
else if(now == ')') {
|
||
while(top >= 0 && stack[top] != '(') {
|
||
char op = pop();
|
||
printf("%c ", op == 'n' ? ' ' : op);
|
||
}
|
||
if(top >= 0) {
|
||
pop(); // 移除左括號
|
||
}
|
||
}
|
||
// 處理運算子
|
||
else if(is_operator(now)) {
|
||
while(top >= 0 && get_priority(stack[top]) >= get_priority(now)) {
|
||
char op = pop();
|
||
printf("%c ", op == 'n' ? ' ' : op);
|
||
}
|
||
push(now);
|
||
}
|
||
|
||
i++;
|
||
}
|
||
|
||
// 輸出堆疊中剩下的所有運算子
|
||
while(top >= 0) {
|
||
char op = pop();
|
||
printf("%c ", op == 'n' ? ' ' : op);
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
printf("=== 中序轉後序計算機 ===\n");
|
||
printf("這個程式可以把一般的算式轉換成後序表示法\n");
|
||
printf("可以使用的符號：+, -, *, /, ^, (, )\n");
|
||
printf("請輸入算式：");
|
||
|
||
gets(input);
|
||
convert_to_postfix();
|
||
|
||
printf("\n");
|
||
return 0;
|
||
}
|