275 lines
7.7 KiB
C
275 lines
7.7 KiB
C
#include <stdio.h>
|
||
#include <stdlib.h>
|
||
#include <string.h>
|
||
#include <math.h>
|
||
#include <ctype.h>
|
||
#define MAX 100
|
||
|
||
// === 全域變數宣告 ===
|
||
char input[MAX];
|
||
char postfix[MAX];
|
||
char stack[MAX];
|
||
double numStack[MAX];
|
||
int top = -1;
|
||
int numTop = -1;
|
||
|
||
// === 函式宣告 ===
|
||
int get_priority(char op);
|
||
int is_operator(char c);
|
||
double calculate(double a, double b, char op);
|
||
void convert_to_postfix();
|
||
double evaluate_postfix();
|
||
double evaluate_infix(char *expr);
|
||
double parse_number(char **expr);
|
||
|
||
// === 檢查運算子優先順序 ===
|
||
//int get_priority(char op) {
|
||
// switch(op) {
|
||
// case '+': case '-': return 1;
|
||
// case '*': case '/': return 2;
|
||
// case '^': return 3;
|
||
// default: return 0;
|
||
// }
|
||
//}
|
||
|
||
int get_priority(char c){
|
||
if(c=='+' || c=='-'){
|
||
return 1;
|
||
}else if(c=='*' || c=='/'){
|
||
return 2;
|
||
}else if(c=='^'){
|
||
return 3;
|
||
}else{
|
||
return 0;
|
||
}
|
||
}
|
||
|
||
|
||
// === 檢查字元是否為運算子 ===
|
||
int is_operator(char c) {
|
||
return (c == '+' || c == '-' || c == '*' || c == '/' || c == '^');
|
||
}
|
||
|
||
// === 執行運算 ===
|
||
double calculate(double a, double b, char op) {
|
||
switch(op) {
|
||
case '+': return a + b;
|
||
case '-': return a - b;
|
||
case '*': return a * b;
|
||
case '/':
|
||
if(b != 0) return a / b;
|
||
printf("錯誤：除數不能為零！\n");
|
||
exit(1);
|
||
case '^': return pow(a, b);
|
||
default: return 0;
|
||
}
|
||
}
|
||
|
||
// === 解析數字（包括浮點數） ===
|
||
double parse_number(char **expr) {
|
||
char *end;
|
||
double result = strtod(*expr, &end);
|
||
*expr = end;
|
||
return result;
|
||
}
|
||
|
||
// === 轉換為後序表達式 ===
|
||
void convert_to_postfix() {
|
||
int i = 0 , j;
|
||
int postfix_index = 0;
|
||
top = -1;
|
||
|
||
// printf("後序表示法：");
|
||
|
||
while(input[i] != '\0') {
|
||
if(isdigit(input[i]) || input[i] == '.' || (input[i] == '-' && (i == 0 || input[i-1] == '(' || is_operator(input[i-1])))) {
|
||
char *end;
|
||
double num = strtod(&input[i], &end);
|
||
int len = end - &input[i];
|
||
printf("%.1f ", num);
|
||
for(j = 0; j < len; j++) {
|
||
postfix[postfix_index++] = input[i+j];
|
||
}
|
||
postfix[postfix_index++] = ' ';
|
||
i += len - 1;
|
||
}
|
||
else if(input[i] == '(') {
|
||
stack[++top] = input[i];
|
||
}
|
||
else if(input[i] == ')') {
|
||
while(top >= 0 && stack[top] != '(') {
|
||
printf("%c ", stack[top]);
|
||
postfix[postfix_index++] = stack[top];
|
||
postfix[postfix_index++] = ' ';
|
||
top--;
|
||
}
|
||
if(top >= 0) top--;
|
||
}
|
||
else if(is_operator(input[i])) {
|
||
while(top >= 0 && stack[top] != '(' &&
|
||
(get_priority(stack[top]) > get_priority(input[i]) ||
|
||
(get_priority(stack[top]) == get_priority(input[i]) && input[i] != '^'))) {
|
||
printf("%c ", stack[top]);
|
||
postfix[postfix_index++] = stack[top];
|
||
postfix[postfix_index++] = ' ';
|
||
top--;
|
||
}
|
||
stack[++top] = input[i];
|
||
}
|
||
i++;
|
||
}
|
||
|
||
while(top >= 0) {
|
||
printf("%c ", stack[top]);
|
||
postfix[postfix_index++] = stack[top];
|
||
postfix[postfix_index++] = ' ';
|
||
top--;
|
||
}
|
||
postfix[postfix_index] = '\0';
|
||
printf("\n");
|
||
}
|
||
|
||
// === 計算後序表達式 ===
|
||
double evaluate_postfix() {
|
||
int i;
|
||
numTop = -1;
|
||
char *token = strtok(postfix, " ");
|
||
|
||
// printf("\n計算過程：\n");
|
||
|
||
while(token != NULL) {
|
||
// printf("處理標記：'%s'\n", token);
|
||
|
||
if(isdigit(token[0]) || (token[0] == '-' && isdigit(token[1]))) {
|
||
double num = atof(token);
|
||
numStack[++numTop] = num;
|
||
// printf("壓入數字：%.2f\n", num);
|
||
}
|
||
else if(is_operator(token[0])) {
|
||
if(numTop < 1) {
|
||
// printf("錯誤：運算子 '%c' 缺少足夠的操作數\n", token[0]);
|
||
exit(1);
|
||
}
|
||
double b = numStack[numTop--];
|
||
double a = numStack[numTop--];
|
||
double result = calculate(a, b, token[0]);
|
||
numStack[++numTop] = result;
|
||
// printf("計算：%.2f %c %.2f = %.2f\n", a, token[0], b, result);
|
||
}
|
||
else {
|
||
// printf("錯誤：未知的標記 '%s'\n", token);
|
||
exit(1);
|
||
}
|
||
|
||
// printf("當前堆疊：");
|
||
for(i = 0; i <= numTop; i++) {
|
||
// printf("%.2f ", numStack[i]);
|
||
}
|
||
// printf("\n\n");
|
||
|
||
token = strtok(NULL, " ");
|
||
}
|
||
|
||
if(numTop != 0) {
|
||
// printf("錯誤：計算結束後堆疊中剩餘 %d 個元素\n", numTop + 1);
|
||
exit(1);
|
||
}
|
||
|
||
return numStack[numTop];
|
||
}
|
||
|
||
// === 直接計算中序表達式 ===
|
||
double evaluate_infix(char *expr) {
|
||
char opStack[MAX];
|
||
double valStack[MAX];
|
||
int opTop = -1;
|
||
int valTop = -1;
|
||
|
||
printf("\n中序計算過程：\n");
|
||
|
||
while(*expr) {
|
||
if(isspace(*expr)) {
|
||
expr++;
|
||
continue;
|
||
}
|
||
|
||
if(isdigit(*expr) || *expr == '.' || (*expr == '-' && (valTop == -1 || opStack[opTop] == '('))) {
|
||
double num = parse_number(&expr);
|
||
valStack[++valTop] = num;
|
||
printf("壓入數字: %f\n", num);
|
||
}
|
||
else if(*expr == '(') {
|
||
opStack[++opTop] = *expr++;
|
||
printf("壓入左括號\n");
|
||
}
|
||
else if(*expr == ')') {
|
||
printf("處理右括號\n");
|
||
while(opTop >= 0 && opStack[opTop] != '(') {
|
||
char op = opStack[opTop--];
|
||
double b = valStack[valTop--];
|
||
double a = valStack[valTop--];
|
||
valStack[++valTop] = calculate(a, b, op);
|
||
printf("計算: %f %c %f = %f\n", a, op, b, valStack[valTop]);
|
||
}
|
||
if(opTop >= 0) opTop--; // 移除左括號
|
||
expr++;
|
||
}
|
||
else if(is_operator(*expr)) {
|
||
while(opTop >= 0 && opStack[opTop] != '(' &&
|
||
(get_priority(opStack[opTop]) > get_priority(*expr) ||
|
||
(get_priority(opStack[opTop]) == get_priority(*expr) && *expr != '^'))) {
|
||
char op = opStack[opTop--];
|
||
double b = valStack[valTop--];
|
||
double a = valStack[valTop--];
|
||
valStack[++valTop] = calculate(a, b, op);
|
||
printf("計算: %f %c %f = %f\n", a, op, b, valStack[valTop]);
|
||
}
|
||
opStack[++opTop] = *expr++;
|
||
printf("壓入運算子: %c\n", *(expr-1));
|
||
}
|
||
else {
|
||
expr++; // 跳過未知字符
|
||
}
|
||
}
|
||
|
||
while(opTop >= 0) {
|
||
char op = opStack[opTop--];
|
||
double b = valStack[valTop--];
|
||
double a = valStack[valTop--];
|
||
valStack[++valTop] = calculate(a, b, op);
|
||
printf("計算: %f %c %f = %f\n", a, op, b, valStack[valTop]);
|
||
}
|
||
|
||
return valStack[valTop];
|
||
}
|
||
|
||
int main() {
|
||
|
||
printf("請輸入中序表示式(支援+-*/^()運算) => ");
|
||
|
||
fgets(input, MAX, stdin);
|
||
input[strcspn(input, "\n")] = 0;
|
||
|
||
printf("\n對應的後序表示法式： ");
|
||
convert_to_postfix();
|
||
double postfix_result = evaluate_postfix();
|
||
printf("\n運算結果：%.2f", postfix_result);
|
||
|
||
printf("\t(正確值為：");
|
||
if(strcmp(input,"10+20*(50-30)/2^4-6*8")==0){
|
||
printf("%g",10+20*(50-30)/pow(2,4)-6*8);
|
||
}else if(strcmp(input,"10+20*(-50+30)/-2^4-6*8")==0){
|
||
printf("%g",10+20*(-50+30)/pow(-2,4)-6*8);
|
||
}else if(strcmp(input,"10.5+20.8*(50.1-30.6)/2.5^4-6.6*8.2")==0){
|
||
printf("%g",10.5+20.8*(50.1-30.6)/pow(2.5,4)-6.6*8.2);
|
||
}else if(strcmp(input,"10.5+20.8*(-50.1+30.6)/2.5^-4-6.6*8.2")==0){
|
||
printf("%g",10.5+20.8*(-50.1+30.6)/pow(2.5,-4)-6.6*8.2);
|
||
}printf(")");
|
||
|
||
// printf("\n=== 中序直接計算 ===\n");
|
||
// double infix_result = evaluate_infix(input);
|
||
// printf("中序計算結果：%f\n", infix_result);
|
||
|
||
return 0;
|
||
}
|